随笔-2  评论-0  文章-0  trackbacks-0
http://acm.hdu.edu.cn/showproblem.php?pid=1050 
题目的地址。
用贪心做的,但是看了DISCUSS发现有很神的办法。
为什么贴上来这道呢。主要是练习赛的时候发现交不了,然后换到主页就A掉了。
RP太差啊。
总体上思路很简单,有点像COJ的今年暑假不AC。
贴代码
  #include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
struct kdq
{
    int start,end;//起始和结束房间号对应的走廊距离
    bool visit;//判断是否已经计算
}time[505];
bool cmp(kdq a,kdq b)
{
    return a.start<b.start;
}
int main()
{
    int i,j,k,l,n,m;
    int T;
    cin>>T;
    int a,b;
    while(T--)
    {
        cin>>n;
        for(i=0;i<n;i++)
        {
            scanf("%d%d",&a,&b);
            a=(a+1)/2,b=(b+1)/2;//房间号对应的走廊距离
            time[i].start=a<b?a:b;
            time[i].end=a>b?a:b;
            time[i].visit=0;
        }
        sort(time,time+n,cmp);//按start从小到大排序
        int start=time[0].end;
        time[0].visit=1;
        int num=0;
        while(1)//贪心
        {
            num++;
            bool flag=0;
            for(i=0;i<n;i++)
            {
                if(!time[i].visit)
                {
                    if(time[i].start>start)
                    {
                        time[i].visit=1;
                        start=time[i].end;
                    }
                }
            }
            for(i=0;i<n;i++)
            {
                if(!time[i].visit)
                {
                    flag=1;
                    start=time[i].end;
                    time[i].visit=1;
                    break;
                }
            }

            if(!flag)
            break;
        }
        cout<<num*10<<endl;
    }
    return 0;
}
posted on 2012-06-30 22:55 invincible 阅读(242) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理