首页 > 代码库 > CF 332 C 贪心

CF 332 C 贪心

题目链接:http://codeforces.com/problemset/problem/332/C


参考  链接: http://blog.csdn.net/cc_again/article/details/9471465


题目意思:


有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;
}


*/