fzu 2007 Selecting courses (The 35th ACM/ICPC Asia Regional Fuzhou Site)贪心+堆

题意:
给出一堆课,选课时间从si到ei,每个学生可以从任意一个时刻开始选课,然后每隔5分钟选一次,如果在某个时刻t,存在某个课程i,si<t,ei>t,那么可以选这门课。问最多可以选多少门课。
解法:
首先注意,选课时间是开区间,(s,e),需要事先处理为[s*2+1,e*2-1]
然后就可以枚举起点然后贪心,每次取覆盖当前时间点的右端点最小的那个区间(课程)来选。
具体实现方法可以先按照s排序,然后建立一个以e为关键字的小根堆,动态统计,这样复杂度O(nlogn)
代码:
 1 # include <cstdio>
 2 # include <queue>
 3 # include <algorithm>
 4 # include <vector>
 5 using namespace std;
 6 int n;
 7 const int N=305;
 8 struct node
 9 {
10    int s,e;
11 }data[N];
12 bool cmp(const node &a,const node &b)
13 {
14    return a.s<b.s;
15 }
16 struct cmp1
17 {
18    bool operator()(const node &a,const node &b) const
19    {
20         return a.e>b.e;
21    } 
22 };
23 int main()
24 {
25     while(true)
26     {
27        scanf("%d",&n);
28        if(!n) break;
29        int start=0xfffffff,end=-1;
30        for(int i=0;i<n;i++)
31        {
32          scanf("%d%d",&data[i].s,&data[i].e);
33          data[i].s=data[i].s*2+1;
34          data[i].e=data[i].e*2-1;
35          start=min(start,data[i].s);
36          end=max(data[i].e,end);
37        }
38        sort(data,data+n,cmp);
39        int res=0;
40        for(int s=start;s<=start+10;s++)
41        {
42           int total=0,p=0;
43           priority_queue<node,vector<node>,cmp1> q;
44           for(int t=s;t<=end;t+=10)
45           {
46              while(p<n&&data[p].s<=t)
47                q.push(data[p++]);
48              while(!q.empty()&&q.top().e<t) q.pop();
49              if(!q.empty())
50              {
51                total++;
52                q.pop();
53              }
54           }
55           res=max(res,total);
56        }
57        printf("%d\n",res);
58     }
59     return 0;
60 }
61 


posted on 2010-12-07 00:09 yzhw 阅读(507) 评论(2)  编辑 收藏 引用 所属分类: data struct

评论

# re: fzu 2007 Selecting courses (The 35th ACM/ICPC Asia Regional Fuzhou Site)贪心+堆[未登录] 2011-03-15 20:03 knight

贪心的思想是每经过5分钟如果有可以选的课,那么就选所有可以选的课中最早结束的那一门课,然后t+=10(5minutes)!可是如果当前时间刚好没有选课(也就是没有选到课,我们不必等5minutes),那么按照题目的意思我们可以对t+=2(1minutes)。这样有错吗?我把你写的code按上面的想法改了,可是不对??
请神牛赐教!
QQ:707089795  回复  更多评论   

# re: fzu 2007 Selecting courses (The 35th ACM/ICPC Asia Regional Fuzhou Site)贪心+堆[未登录] 2011-03-15 20:12 knight

好像是我题目看错了!  回复  更多评论   


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


<2010年10月>
262728293012
3456789
10111213141516
17181920212223
24252627282930
31123456

导航

统计

公告

统计系统

留言簿(1)

随笔分类(227)

文章分类(2)

OJ

最新随笔

搜索

积分与排名

最新评论

阅读排行榜