题意如下:
告诉你有400个房间,如上图所示。给你一个数n,下面给出n个桌子要搬(从i房间搬到j房间),要你求出最小要用多少时间搬这些桌子?数据范围:(1 <= n <= 200) (1 <= i,j <= 400)如下附件图所示:
思路:
观察下附件图,可知1,2 shared,3,4 shared……399,400shared;不难可以将1和2,3和4^399和400认为是一个房间,这样可以减少一半。这样问题就简化到求从i位置到j位置搬桌子。考虑到n不是很大,可以模拟来做。
首先开一个数组全部置为0,i到j搬桌子(此时的i,j要变成(i + 1) / 2,(j + 1) / 2),就把a[i]到a[j]之间的所有值加1;最后数组中最大的那个值就是所要求的时间,当然还要再乘以10。我此题的理解在于(i+1)/2处,举个例子,从如(29,50)与(30,49)本质上的个数是一样的,由于奇数偶数可以相互共享,则数目应该少一半等于(15,25)这是迷惑我的关键,不好意思,刚做ACM 有点水。
代码如下:
#include <iostream>
#include <stdlib.h>
using namespace std;
int main()
{
int n,m,a,b,i,j;
cin>>n;
while (n--)
{
int c[201];
memset(c,0,201);
cin>>m;
for (i=0;i<m;i++)
{
cin>>a>>b;
if (a>b)
swap(a,b);
for (j=(a+1)/2;j<=(b+1)/2;j++)
c[j]++;
}
int max=-1;
for (i=0;i<201;i++)
if (c[i]>max)
max=c[i];
cout<<max*10<<endl;
}
return 0;
}
- 大小: 23.4 KB
分享到:
相关推荐
北大POJ水题整合包 解题报告+AC代码
北大 POJ的水题解答C++版,请合理使用
POJ 1006 源代码——中国剩余定理分析POJ 1006 源代码——中国剩余定理分析POJ 1006 源代码——中国剩余定理分析
The island nation of Flatopia is perfectly flat. Unfortunately, Flatopia has no public highways. So the traffic is difficult in Flatopia. The Flatopian government is aware of this problem....
POJ水题集-----50道左右-----增加自信啊..
我进行挑选的 希望能给你带来方便 也希望你能通过这个有所提高
POj 1001源代码——高精度乘单精度POj 1001源代码——高精度乘单精度POj 1001源代码——高精度乘单精度POj 1001源代码——高精度乘单精度
poj 2488——dfs深度优先遍历 //给行数列数,求问能否遍历,给出字典序的一种遍历
poj水题的部分代码,做的还是比较靠谱的
poj训练 c语言poj训练 西工大 poj 100题。
POJ各题算法分类和题目推荐 ACM必看 POJ各题算法分类和题目推荐 ACM必看 POJ各题算法分类和题目推荐 ACM必看
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
POJ1083的代码,POJ1083的代码,POJ1083的代码
poj部分水题代码描述,为初学者提供一些必要的基础
POJ 是“北京大学程序在线评测系统”(Peking University Online Judge)的缩写,是个提供编程题目的网站,兼容Pascal、C、C++、Java、Fortran、Python等多种语言。可以按照分类,在POJ上做题。
POJ入门题库,有源代码,部分有解题思路,还有输出截图
POJ100题详细解题报告
北京大学数据结构与算法课程作业代码,供广大学习c++的同学参考与学习
北京大学数据结构与算法课程作业代码,供广大学习c++的同学参考与学习
acm pku poj 1000 1001 1002 1003 1201