Blog·Tanky WooABOUTRSS

HDOJ 1050 Moving Tables

21 Jul 2010
这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。

题目地址:

http://acm.hdu.edu.cn/showproblem.php?pid=1050

又是一道贪心题,不过和 HDOJ 1009HDOJ 2037不一样,这里是以局部最优反映了整体最优。

而其余2题是逐步求最优,不知道说清楚没,做了这三题就可以感觉出来了,这三题都是很经典的题目。

这题看见有人用类似上面2题的方法做了,我没去尝试,看见杭电的PPT里有更简单的方法,尝试了,写出来的代码简单易懂。

思路:首先要知道,最长的时间就是一个过道被经过的最大次数,这样题目就简单多了,求过道重复次数最大值,这里注意1,2和3,4等都是对门的,要采用减一后除以2的方法映射到同一坐标轴上。

 #include 
#include 
using namespace std;

// Author: Tanky Woo
// HDOJ 1050
// 0MS 180K 748B 
int T, N;
int possible[201];
// www.wutianqi.com
int main()
{
    //freopen("input.txt", "r", stdin);
    scanf("%d", &T;);
    int s, t;
    while(T--)
    {
        memset(possible, 0, sizeof(possible));
        scanf("%d", &N;);
        for(int i = 0; i < N; ++i)
        {
            scanf("%d %d", &s;, &t;);
            // 注意这里不是简单的s到t,因为1,2是相对的。
            // 所以,减一后除以2可以把1,2;3,4等对应到同一坐标轴上.
            s = (s-1)/2;
            t = (t-1)/2;
            if(s > t)
            {
                s += t;
                t = s-t;
                s -=t;
            }
            for(int j = s; j <= t; ++j)
                possible[j]++;
        }

        int max_sum = -1;
        // 不知道这算不算局部最优求正题最优,个人觉得是这样的吧
        for(int i = 0; i < 201; ++i)   //求出哪块区域最大,也就是占用时间最长
            if(possible[i] > max_sum)
                max_sum = possible[i];
        printf("%d\n", max_sum*10);
    }
    return 0;
}