首页 > 代码库 > CF 332 C 贪心
CF 332 C 贪心
题目链接:http://codeforces.com/problemset/problem/332/C
题目意思:
有n个命令,要通过p个,某主席要在通过的p个中选择k个接受。
每个任务有两个值ai,bi, ai表示如果该主席接受该命令,她的头发变灰的数量,bi表示如果该主席不接受该命令时,议员不高兴值。
对于通过的p个命令,该主席要使议员的不高兴值和最小,在相同的情况下,要使自己的头发变灰的数量尽可能的少。
题目意思:
有n个命令,要通过p个,某主席要在通过的p个中选择k个接受。
每个任务有两个值ai,bi, ai表示如果该主席接受该命令,她的头发变灰的数量,bi表示如果该主席不接受该命令时,议员不高兴值。
对于通过的p个命令,该主席要使议员的不高兴值和最小,在相同的情况下,要使自己的头发变灰的数量尽可能的少。
让你求出通过哪p个命令,使得该主席的头发变灰的数量最多,在相同的情况下,输出使议员不高兴最大的选择。
解题思路:
非常关键的一点是主席的想法和我们不同,我们先选出主席一定不会通过的p-k条命令来,那么这p-k条命令必须
unhappy最小,然后那k条必须选的选择num(白头发数量)最多的,这样头发多的选出来了,再更新那不选的p-k条,大致思路
说完了,看代码吧:
/* 题目意思: 有n个命令,要通过p个,某主席要在通过的p个中选择k个接受。 每个任务有两个值ai,bi, ai表示如果该主席接受该命令,她的头发变灰的数量,bi表示如果该主席不接受该命令时,议员不高兴值。 对于通过的p个命令,该主席要使议员的不高兴值和最小,在相同的情况下,要使自己的头发变灰的数量尽可能的少。 让你求出通过哪p个命令,使得该主席的头发变灰的数量最多,在相同的情况下,输出使议员不高兴最大的选择。 */ // 好难的贪心 #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define N 101000 struct stud{ int num,unhappy; int pos,pp; }f[N],s[N]; int n,p,k,vis[N]; int ans[N]; int cmp1(stud a,stud b) //按照主席的习惯,先选不高兴多,然后掉头发也少的 { if(a.unhappy==b.unhappy) return a.num<b.num; return a.unhappy>b.unhappy; } int cmp2(stud a,stud b) //按照我们意愿,选头发掉的多,为什么unhappy大的在前面呢,请看cmp1,unhappy大的在前面, //我们找到前面的unhappy最小的越大,后面掉头发的unhappy的选择越大, { if(a.num==b.num) return a.unhappy>b.unhappy; return a.num>b.num; } int main() { int i; while(~scanf("%d%d%d",&n,&p,&k)) { for(i=1;i<=n;i++) { scanf("%d%d",&f[i].num,&f[i].unhappy); f[i].pos=i; } sort(f+1,f+n+1,cmp1);//按不高兴减序,白头发增序 memcpy(s,f,sizeof(f)); //请记住,一定要开另一个结构体,不要像我下面的一样,因为cmp2排序后再cmp1可能不是这个序列了 for(i=1;i<=n;i++) f[i].pp=i; sort(f+1,f+n-(p-k)+1,cmp2); //留下最少逼迫主席选前面num大的p-k个(暂时逼迫主席的,后面会更新) int j=1; for(i=1;i<=k;i++) { j=max(j,f[i].pp); if(i==1) printf("%d",f[i].pos); else printf(" %d",f[i].pos); } sort(s+j+1,s+n+1,cmp1); for(i=j+1;i<=j+p-k;i++) printf(" %d",s[i].pos); printf("\n"); } return 0; } //附上一份让我自己写的吐血的错误代码 //就是没有开两个数组,wa到死 /* #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define N 100005 struct stud{ int hair,anger; int pos,pp; }f[N]; int n,p,k; int cmp1(stud a,stud b) { if(a.anger==b.anger) return a.hair<b.hair; return a.anger>b.anger; } int cmp2(stud a,stud b) { if(a.hair==b.hair) return a.anger>b.anger; return a.hair>b.hair; } int main() { int n,i; while(~scanf("%d%d%d",&n,&p,&k)) { for(i=1;i<=n;i++) { scanf("%d%d",&f[i].hair,&f[i].anger); f[i].pos=i; } sort(f+1,f+n+1,cmp1); for(i=1;i<=n;i++) f[i].pp=i; sort(f+1,f+n+1-(p-k),cmp2); int j=1; for(i=1;i<=k;i++) { if(i==1) printf("%d",f[i].pos); else printf(" %d",f[i].pos); j=max(j,f[i].pp); } sort(f+1,f+n+1,cmp1); sort(f+j+1,f+n+1,cmp1); for(i=j+1;i<=j+p-k;i++) printf(" %d",f[i].pos); printf("\n"); } return 0; } */
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。