Demonstration(CodeForces-191B)【贪心】

题目链接：https://vjudge.net/problem/CodeForces-191B

题意：过于繁琐，略

思路：真·神级贪心题

　　首先我们可以想到的是，为了在k天内选到最靠前的城市，我们要想办法在前k-1天挑选尽可能贵的城市，为第k天奠定基础。

　　先对前n-1个城市的举办活动价值排序，对前k大的求和得到sum，接下来：

　　<1>sum>=0,则不论前k-1天选择多么贵的城市，第k天都无法找到一个城市花光政府的钱，那么只能选择最差的城市

　　<2>sum<0,按序号由小到大判断该城市是否包含在sum中或者将sum的第一项替换为该城市后sum仍小于0，如果满足条件，则该城市则为最优解

代码如下：

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 int n,k,a[],val[];

 long long b;

 int main(){

     scanf("%d%d%I64d",&n,&k,&b);

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

         scanf("%d",&a[i]);

         val[i]=a[i];

     }

     sort(val+,val+n);

     long long sum=b;

     for(int i=n-;i>=n-k;i--)

         sum-=val[i];

     if(sum>=){

         printf("%d",n);

     }

     else {

         int ans=-;

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

             if(a[i]>=val[n-k]||sum+val[n-k]-a[i]<){

                 ans=i;

                 break;

             }

         }

         printf("%d",ans);

     }

     return ;

 }

巴特西

Demonstration(CodeForces-191B)【贪心】

最新文章

热门文章