首页 > 代码库 > hdu 5360 Hiking(优先队列+贪心)
hdu 5360 Hiking(优先队列+贪心)
题目:http://acm.hdu.edu.cn/showproblem.php?
pid=5360
题意:beta有n个朋友,beta要邀请他的朋友go hiking,已知每一个朋友的理想人数[L,R](现有L~R个人准备去,那么这个朋友就去)。
求最多有多少人去。
及beta邀请朋友的顺序。
分析:每次邀请人的最优解就是:选会去的人里面R最小的那个人。
代码实现的话,cur代表已经准备go hiking的人数,每次将全部L<=cur的人放进优先队列,选出R最小的那个。
假设队列为空,那么剩下的全部人将不会去,假设先出的那个人的[L,R]不满足条件,那么这个人以后也不会去go hiking,所以还是将他选出,仅仅是去go hiking的人数不增。
代码:
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <queue> using namespace std; const int maxn = 1e5+5; struct node { int L,R,id; bool operator < (const node &t) const { return R>t.R; } }s[maxn]; bool cmp(node a,node b) { if(a.L!=b.L) return a.L<b.L; return a.R<b.R; } int ans[maxn]; priority_queue <node > q; int main() { int ncase,n,i,j,cur,cnt; scanf("%d",&ncase); while(ncase--) { scanf("%d",&n); for(i=1;i<=n;i++) scanf("%d",&s[i].L); for(i=1;i<=n;i++) { scanf("%d",&s[i].R); s[i].id=i; } sort(s+1,s+1+n,cmp); cur=0; cnt=1; i=1; while(!q.empty()) q.pop(); while(1) { while(i<=n && s[i].L<=cur) q.push(s[i++]); if(q.empty()) break; node temp=q.top(); q.pop(); if(temp.L<=cur && temp.R>=cur) cur++; ans[cnt++]=temp.id; } for(;i<=n;i++) ans[cnt++]=s[i].id; printf("%d\n",cur); printf("%d",ans[1]); for(i=2;i<=n;i++) printf(" %d",ans[i]); printf("\n"); } return 0; }
hdu 5360 Hiking(优先队列+贪心)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。