题解 CF976E 【Well played!】

2019-02-14 16:33:20


题目意思,也就是说,如果你场上有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;
}