Codeforces 976E 题解报告

朱雀 2022-05-25 00:47 178阅读 0赞

# 一、题目 #

[http://codeforces.com/contest/976/problem/E][http_codeforces.com_contest_976_problem_E]

# 二、分析 #

（1）当把所有的倍数2 ^ a都加到同一health上，health增加的最多  
（2）先计算每一个creature的hp - dmg，按该值对所有的creature排序  
再求和，i

# 三、程序 #

#include <bits/stdc++.h>
    using namespace std;
    
    const int N = 200 * 1000 + 9;
    int hp[N], dmg[N];
    
    // 按生命值和破坏值的差排序，差大的排在前
    // 若差相等，按原先的顺序即从小到大
    bool cmp(int i, int j)
    {
        if(hp[i] - dmg[i] != hp[j] - dmg[j])
        {
            return hp[i] - dmg[i] > hp[j] - dmg[j];
        }
        return i < j;
    }
    
    // 得到生命值和破坏值中的较大者
    int getMaxDesc(int id)
    {
        return  hp[id] > dmg[id] ? hp[id] : dmg[id];
    }
    
    int main()
    {
        int n, a, b;
        scanf("%d %d %d", &n, &a, &b);
        for(int i = 0; i < n; ++i)
        {
            scanf("%d %d", hp + i, dmg + i);
        }
    
        b = min(b, n);
        vector <int> creature(n);
        for(int i = 0; i < n; ++i)
        {
            creature[i] = i;
        }
    
        // 按creature的生命值和破坏值的差进行排序
        sort(creature.begin(), creature.end(), cmp);
    
        long long res = 0, sum = 0;
        for(int i = 0; i < n; ++i)
        {
            int id = creature[i];
    
            /* * 初始不考虑a * i<b，可以把生命值赋值给破坏值 * i>=b，不能把生命值赋值给破坏值 */
            if(i < b)
            {
                sum += getMaxDesc(id);
            }
            else
            {
                sum += dmg[id];
            }
        }
        res = sum;
    
        if(b == 0)
        {
            printf("%I64d\n", res);
            return 0;
        }
    
        // 所有的a加给同一creature时翻倍最多，倍数为2的a次幂
        long long mutiple = (1LL << a);
        for(int i = 0; i < n; ++i)
        {
            int id = creature[i];
            long long newsum = sum;
    
            if(i < b)
            {
                // 挨个用翻倍后的生命值来替换，看看哪个最大
                newsum -= getMaxDesc(id);
                newsum += hp[id] * mutiple;
                res = max(res, newsum);
            }
            else
            {
                // 因为排过序，在0~b-1步中，第b-1步获得的破坏值是最小的
                // 先让第b-1步不用生命值替换，直接取破坏值
                // 这样就获得了一次替换的机会
                int id2 = creature[b - 1];
                newsum -= getMaxDesc(id2);
                newsum += dmg[id2];
    
                // 利用上一步得来的替换机会，用翻倍后的生命值替换破坏值，看看哪个最大
                newsum -= dmg[id];
                newsum += hp[id] * mutiple;
    
                res = max(res, newsum);
            }
        }
    
        printf("%I64d\n", res);
        return 0;
    }

> TopCoder & Codeforces & AtCoder交流QQ群：648202993  
> 更多内容请关注微信公众号  
> ![wechat\_public\_header.jpg][wechat_public_header.jpg]

[http_codeforces.com_contest_976_problem_E]: http://codeforces.com/contest/976/problem/E
[wechat_public_header.jpg]: /images/20220525/f78babe7d9a1494997700a128aab2afc.png