贪心 CF 332 C 好题赞

题目链接：

http://codeforces.com/problemset/problem/332/C

题目意思：

有n个命令，要通过p个，某主席要在通过的p个中选择k个接受。

每个任务有两个值ai,bi, ai表示如果该主席接受该命令，她的头发变灰的数量，bi表示如果该主席不接受该命令时，议员不高兴值。

对于通过的p个命令，该主席要使议员的不高兴值和最小，在相同的情况下，要使自己的头发变灰的数量尽可能的少。

让你求出通过哪p个命令，使得该主席的头发变灰的数量最多，在相同的情况下，输出使议员不高兴最大的选择。

解题思路：

很好的一道贪心题目。

首先须知道，对于每一个选择（p命令），该主席一定是把b值最小的p-k个留下，如果有相同的，则尽可能使自己的头发变灰的数量最小。

为了先使该主席的suma最大，先按b从大到小排序，有相同的则按a从小到大排序。把后面p-k个留下，这样就一定可以确保suma尽可能大，因为对于后面的b较小的p-k个,无论a有多大，如果选它都没用，a不能发挥作用，所以只能从前n-(p-k)个里选。所以再把前n-(p-k)个按a从大到小排序，如果a相等则按b从大到小（把小的b尽可能靠后，为了在相同的a的情况下，sumb尽可能的大）。选出前k个输出（这就是最大的suma),然后在最大的suma的情况下，把最小的b的下标找到，然后对后面的所有小b的情况，按b从大到小排序，选出最大的p-k个。

标注红颜色的那句话，很关键。如果b有相等的情况，如果按a从大到小排序，虽然这时候算出的suma可能更大，可是，当这样的p个命令确定后，当b相同的情况下，该主席肯定会选a大的。所以这时算的suma就不准确，所以应该按a从小到大排序。

写的有点啰嗦，但应该说清楚了。

主要思想：

当有两个优先级不同的限制条件时，先以第二优先级的最坏的打算来保证第一优先级，再在第一优先级得到满足条件下，来使得第二优先条件（本题是愤怒值最大）得到满足。

代码：

#include<iostream>

#include<cmath>

#include<cstdio>

#include<cstdlib>

#include<string>

#include<cstring>

#include<algorithm>

#include<vector>

#include<map>

#include<set>

#include<stack>

#include<list>

#include<queue>

#define eps 1e-6

#define INF 0x1f1f1f1f

#define PI acos(-1.0)

#define ll __int64

#define lson l,m,(rt<<1)

#define rson m+1,r,(rt<<1)|1

//#pragma comment(linker, "/STACK:1024000000,1024000000")

using namespace std;

/*

freopen("data.in","r",stdin);

freopen("data.out","w",stdout);

*/

#define N 101000

int n,k,p;

struct Inf

{

   int ai,bi,ii,bbii;

}inf1[N],inf2[N];

bool cmp2(struct Inf a,struct Inf b)

{

   if(a.ai!=b.ai)

      return a.ai>b.ai;

   return a.bi>b.bi;   //尽量把愤怒值小的往后放

}

bool cmp1(struct Inf a,struct Inf b)

{

   if(a.bi!=b.bi)

      return a.bi>b.bi;

   return a.ai<b.ai;    //从主席这一方面考虑，在相同的愤怒值中，他会选a小的那个命令

}

//本题是难得的贪心好题，

//当有多个优先级不同的限制条件时，先以最坏的打算来保证第一优先级条件，再在第一优先条件下，来使得第二优先条件（本题是愤怒值最大）得到满足

int main()

{

   while(scanf("%d%d%d",&n,&p,&k)!=EOF)

   {

      for(int i=1;i<=n;i++)

      {

         scanf("%d%d",&inf1[i].ai,&inf1[i].bi);

         inf1[i].ii=i;

      }

      sort(inf1+1,inf1+n+1,cmp1);

      memcpy(inf2,inf1,sizeof(inf1));

      for(int i=1;i<=n;i++)

         inf1[i].bbii=i;

      sort(inf1+1,inf1+n-(p-k)+1,cmp2);//保证后面至少有p-k个，使得先最大化suma

      int j=0;

      for(int i=1;i<=k;i++)

      {

         printf("%d ",inf1[i].ii); //先保证最大化a

         j=max(j,inf1[i].bbii); //把最小的b找到

      } //在最大化suma的同时，要考虑当相等的suma时，要使sumb尽可能大

      sort(inf2+j+1,inf2+n+1,cmp1);//重新选择sumb

      for(int i=j+1;i<=j+(p-k);i++)

         printf("%d ",inf2[i].ii);

      putchar('\n');

   }

   return 0;

}

巴特西

贪心 CF 332 C 好题赞

最新文章

热门文章

巴特西

贪心 CF 332 C 好题 赞

最新文章

热门文章

贪心 CF 332 C 好题赞