Codeforces976E Well played! 【贪心】

秒速五厘米 2021-10-01 02:34 212阅读 0赞

题目分析：

由于乘二的收获很大，所以我们可以证明乘的数一定是同一个，接着排序后依次选取，判断一下即可。

题目代码：

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 
     4 const int maxn = 320000;
     5 
     6 int n,a,b;
     7 
     8 struct node{
     9     int hp,dm;
    10 }d[maxn];
    11 
    12 int cmp(node alpha,node beta){
    13     return alpha.hp-alpha.dm > beta.hp-beta.dm;
    14 }
    15 
    16 void read(){
    17     scanf("%d%d%d",&n,&a,&b);
    18     for(int i=1;i<=n;i++) scanf("%d%d",&d[i].hp,&d[i].dm);
    19     sort(d+1,d+n+1,cmp);
    20 }
    21 
    22 void work(){
    23     int hh = 1;
    24     long long ext = 0,ans = 0;
    25     for(int i=1;i<=a;i++) hh *= 2;
    26     int pt;
    27     for(pt=1;pt<=min(b,n);pt++){
    28     if(d[pt].hp-d[pt].dm <= 0) break;
    29     ans += d[pt].hp;
    30     }
    31     for(int i=pt;i<=n;i++) ans += d[i].dm;
    32     long long em = ans;ext = ans;pt--;
    33     if(b == 0){printf("%lld",ext);return;}
    34     for(int i=1;i<=n;i++){
    35     em = ans;
    36     if(i<=pt){
    37         em = em-d[i].hp+(1ll*d[i].hp*hh);
    38         ext = max(ext,em);
    39     }else{
    40         if(pt < b){
    41         em = em+(1ll*d[i].hp*hh)-d[i].dm;
    42         ext = max(ext,em);
    43         }else{
    44         em = em-d[pt].hp+(1ll*d[i].hp*hh)-d[i].dm+d[pt].dm;
    45         ext = max(ext,em);
    46         }
    47     }
    48     }
    49     printf("%lld",ext);
    50 }
    51 
    52 int main(){
    53     read();
    54     work();
    55     return 0;
    56 }

转载于:https://www.cnblogs.com/Menhera/p/8982499.html

发表评论取消回复

表情：

评论列表（有 0 条评论，212人围观）

还没有评论，来说两句吧...

相关阅读

相关 codeforces C. Bits 贪心

C. Bits time limit per test 1 second memory limit per test 256 megabytes input sta

偏执的太偏执、/ 2022年07月24日 09:16/ 0 赞/ 202 阅读

相关 codeforces 276D 贪心

D. Little Girl and Maximum XOR time limit per test 2 seconds memory limit per test 2

妖狐艹你老母/ 2022年07月24日 06:26/ 0 赞/ 180 阅读

相关 CodeForces 873C(贪心)

问题描述: Ivan is playing a strange game. He has a matrix a with n rows and m columns. Eac

深藏阁楼爱情的钟/ 2022年06月07日 12:49/ 0 赞/ 151 阅读

相关 Codeforces 191B（贪心)

问题描述: In the capital city of Berland, Bertown, demonstrations are against the recent el

不念不忘少年蓝@/ 2022年06月07日 03:43/ 0 赞/ 222 阅读

相关 Codeforces 976C 题解报告

一、题目 [http://codeforces.com/contest/976/problem/C][http_codeforces.com_contest_976_pr

柔情只为你懂/ 2022年05月26日 13:12/ 0 赞/ 187 阅读

相关 Codeforces 976E 题解报告

一、题目 [http://codeforces.com/contest/976/problem/E][http_codeforces.com_contest_976_pr

朱雀/ 2022年05月25日 00:47/ 0 赞/ 194 阅读

相关 codeforces1187E

题目链接：[http://codeforces.com/problemset/problem/1187/E][http_codeforces.com_problemset_pr

川长思鸟来/ 2021年12月13日 03:21/ 0 赞/ 176 阅读

相关 Codeforces 353E 贪心

题意：给你一张有向图，第i条边连接i号点和(i + 1) % n号点，问最多可以选择多少个点，使得这些点互相不可达。思路：容易发现，如果某个边的集合点的数目大于等于2，那么

妖狐艹你老母/ 2021年12月12日 02:04/ 0 赞/ 248 阅读

相关 Codeforces 867 E. Buy Low Sell High （贪心+优先队列）

You can perfectly predict the price of a certain stock for the next N days. You would li

末蓝、/ 2021年12月05日 15:11/ 0 赞/ 250 阅读

相关 Codeforces976E Well played! 【贪心】

题目分析：　　由于乘二的收获很大，所以我们可以证明乘的数一定是同一个，接着排序后依次选取，判断一下即可。题目代码： 1 include<bits/stdc++

秒速五厘米/ 2021年10月01日 02:34/ 0 赞/ 213 阅读