设为首页 加入收藏

TOP

hdu 1050 Moving Tables
2014-11-23 21:42:19 来源: 作者: 【 】 浏览:2
Tags:hdu 1050 Moving Tables


这个题我首先直接用的常规贪心,用的和那个尽可能看更多完整节目那种思路。但是。。。。。。。一直WA。。。。T_T。。。。
后来在网上搜了一下这个题,发现好多人都有问题,都没有求出来,基本上都用的对尾部排序求的方法。
其实这个题因为是两排房间,所以1和2公用一个走廊,其中一个在需要移动的时候宁外一个还是不能移动。
所以我后面改了思路,直接改成了用两次排序直接找里面重叠部分最多的。(尾部排序的时候也要处理走廊的问题。)


AC了的代码:

#include
#include
#include
#include

using namespace std;

struct Node
{
    int s,t;
    int p;
} a[210];

bool cmp(Node a, Node b)
{
    return a.t < b.t;
}

int main()
{
    int t,n,i,j,tim,ma;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(i = 0; i < n; i++)
        {
            a[i].p = 0;
            scanf("%d%d",&a[i].s,&a[i].t);
            a[i].s = (a[i].s + 1) / 2;  //处理奇偶公用一个走量的情况(这个一直没考虑,所以WA)
            a[i].t = (a[i].t + 1) / 2;
            if(a[i].s > a[i].t)  //保证 s < t
            {
                j = a[i].s;
                a[i].s = a[i].t;
                a[i].t = j;
            }
        }
        sort(a,a+n,cmp);
        ma = 0;
        for(i = 0; i < n; i++)
        {
            tim = 1;
            for(j = i+1; j < n; j++)
            {
                if(a[j].s <= a[i].t)//判断是否有重叠
                {
                    tim++;  //增加一个重叠
                }
            }
            if(tim > ma)
            {
                ma = tim;
            }
        }
        printf("%d\n",ma*10);
    }

    return 0;
}

】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
分享到: 
上一篇hdu 4635 Strongly connected(Tar.. 下一篇HDU 1010――tempter of the bone

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

·Redis on AWS:Elast (2025-12-27 04:19:30)
·在 Spring Boot 项目 (2025-12-27 04:19:27)
·使用华为开发者空间 (2025-12-27 04:19:24)
·Getting Started wit (2025-12-27 03:49:24)
·Ubuntu 上最好用的中 (2025-12-27 03:49:20)