Codeforces976E Well played! 【贪心】-蒲公英云

Codeforces976E Well played! 【贪心】

题目分析：

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

题目代码：

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 }