Codeforces976E Well played! 【贪心】

秒速五厘米 2021-10-01 02:34 283阅读 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 条评论，283人围观）

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

相关阅读

相关 CodeForces1154E

[CodeForces1154E][] 题意就是有两个教练,每个教练轮流操作,每次操作会选取所有未被选取的学生中能力值最高的那一个并把这个学生向左向右各\\(k\\)个学生

落日映苍穹つ/ 2023年06月02日 11:58/ 0 赞/ 60 阅读

相关 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 赞/ 266 阅读

相关 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 赞/ 255 阅读

相关 Codeforces 191B（贪心)

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

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

相关 Codeforces 976C 题解报告

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

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

相关 Codeforces 976E 题解报告

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

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

相关 codeforces1187E

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

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

相关 Codeforces 353E 贪心

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

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

相关 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 赞/ 313 阅读

相关 Codeforces976E Well played! 【贪心】

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

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