当前位置: 代码迷 >> 综合 >> HDOJ-1050 Moving Tables (贪心算法)
  详细解决方案

HDOJ-1050 Moving Tables (贪心算法)

热度:27   发布时间:2023-12-09 20:52:02.0

题目: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;
}
  相关解决方案