题解 CF976E 【Well played!】

题目意思，也就是说，如果你场上有n个怪，你有a张神圣之灵，b张心灵之火，那么请问，怎么能使场攻最大呢！哈哈哈天才！！ 一开始以为这是一道DP题，结果比赛完爆0后，才知道原来是一道纯贪心 可以证明，把所有的翻倍都弄到一个身上，最后的结果是最大的。 剩下的使攻击力与血量相等的次数，全部分配到其他血量大于攻击力的精灵上即可。 但其实这道题有很多的小细节。比如要把翻倍放后面处理，不然就搞不清楚，究竟多少还剩~~多少张心灵之火~~多少次赋值生命值的次数了。 ``` #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define int long long using namespace std; struct node { int x,y; }q[200100]; int n,a,b,sum=0; bool cmp(node c,node d) {return c.x-c.y>d.x-d.y;} signed main() { // freopen("match.in","r",stdin); // freopen("match.out","w",stdout); scanf("%I64d%I64d%I64d",&n,&a,&b); for (int i=1;i<=n;i++) scanf("%I64d%I64d",&q[i].x,&q[i].y); sort(q+1,q+n+1,cmp);//先按差值进行排序后，处理好那些要被赋值 for(int i=1;i<=b;i++) sum+=max(q[i].x,q[i].y); for(int i=b+1;i<=n;i++) sum+=q[i].y; int ans=sum;//对每一个精灵枚举一遍翻倍，然后要被赋值的算增加值时，要减的是攻击力和生命值较大的那一个（因为前面加的时候是这么加的），不被赋值的直接减去攻击力就可以了。 for(int i=1;i<=b;i++) ans=max(ans,sum-max(q[i].x,q[i].y)+(q[i].x<<a)); sum=sum-max(q[b].x,q[b].y)+q[b].y; for(int i=b+1;i<=n && b;i++) ans=max(ans,sum-q[i].y+(q[i].x<<a)); printf("%I64d",ans); return 0; } ```