推桌子
时间限制: 1000 ms | 内存限制:65535 KB
难度: 3
- 描述
- The famous ACM (Advanced Computer Maker) Company has rented a floor of a building whose shape is in the following figure.
- 输入
- The input consists of T test cases. The number of test cases ) (T is given in the first line of the input file. Each test case begins with a line containing an integer N , 1 <= N <= 200, that represents the number of tables to move. Each of the following N lines contains two positive integers s and t, representing that a table is to move from room number s to room number t each room number appears at most once in the N lines). From the 3 + N -rd line, the remaining test cases are listed in the same manner as above. 输出
- The output should contain the minimum time in minutes to complete the moving, one per line. 样例输入
-
3 4 10 20 30 40 50 60 70 80 2 1 3 2 200 3 10 100 20 80 30 50
样例输出 -
102030 题目大意:让你搬桌子,但是走廊太窄,某段走廊只能一次移动一个桌子,两个相对的房间对应同一个走廊号。每次搬运花费10分钟,问最少需耗费多少分钟。其实问的就是次数。 解题思路: 方法1:其实就是重叠度的问题。重叠度越高,需要的次数就越多。可以让每次搬运经过的走廊号对应的变量都自加,最后统计所有走廊号对应变量大小,其中最大的就是需要搬运的最少次数。 方法2:按照选择不相交区间的思想来做。但是这个需要按照左端点从小到大排序,然后挑出第一个没选择过的区间的右端点作为比较值,以挑出的那个区间为衡量选出所有不相交的区间,表示需搬运一次。然后重复挑选。最后挑选了几次,表示需要搬运几次。 1:
//方法1#include
using namespace std;int corridor[210];int main(){ int t,n,m,i,j,k,cnt,tmp,a,b; scanf("%d",&t); while(t--){ memset(corridor,0,sizeof(corridor)); scanf("%d",&n); for(i=0;i b){ tmp=a; a=b; b=tmp; } for(j=a;j<=b;j++){ corridor[j]++; } } cnt=0; for(i=1;i<=202;i++){ cnt>corridor[i]? :cnt=corridor[i]; } cout< < 2:
//方法2#include
using namespace std;struct SEG{ int left,right; int used; SEG(){ used=0; }}seg[500];bool cmp(SEG a,SEG b){ if(a.left!=b.left) return a.left b?a=a+b,b=a-b,a=a-b:0; seg[i].left=a,seg[i].right=b; } sort(seg,seg+n,cmp); num=0,cnt=0; while(cnt