题目:HDOJ-1050
题目描述:
南北各200个房间,编号1~400,从一个房间搬桌子到另一个房间都要10分钟,路径有重合部分(包括端点)的不能同时搬,求最少需要多少时间把要搬的桌子搬完。
思路:
一开始就想着排序,区间不相交,依次模拟着来算时间,但是这样很麻烦。
看了下别人的题解,完美地把问题化简了,一步到位。
因为如果有某个区间被n个搬桌子的任务覆盖了,那么无论如何都必须要n次才能搬完,那么只需要找到这个最大的n,即是能够达成的最少的搬动次数。
这样就把问题转化了为求最多数量的覆盖区间问题。
以下AC代码:
#include<cstdio>
#include<string.h>
#include<algorithm>
using namespace std;
int main()
{
int T;scanf("%d", &T);while (T--){
int x[201], N,i,j, a, b,ans;memset(x, 0,sizeof(x));ans = 0;scanf("%d", &N);for (i = 1; i <= N; i++){
scanf("%d%d", &a, &b);a = (a + 1) / 2; //房间号转化为坐标b = (b + 1) / 2;for (j=min(a,b);j<=max(a,b);j++) //经过的坐标均+1x[j]++;}for (i = 1; i <= 200; i++) //找到最大的坐标{
if (x[i] > ans)ans = x[i];}printf("%d\n", ans*10); //乘上一次10分钟,输出}return 0;
}