Codeforces 976E 题解报告

一、题目

http://codeforces.com/contest/976/problem/E

二、分析

(1)当把所有的倍数2 ^ a都加到同一health上,health增加的最多 (2)先计算每一个creature的hp - dmg,按该值对所有的creature排序 再求和,i=b时只能取dmg。这个和里包含了第2种魔法操作,但没包含第一种魔法操作。 然后进行第一种魔法操作,对于每个creature,逐个使用用hp * 2 ^ a来替换dmg,注意i < b时,直接替换即可,i >= b时,要将前b个creature中hp - dmg最小的那个(因为排过序,第b - 1个creature的hp - dmg最小)机会腾出来,这样后面的creature才能把乘以2 ^ a后的hp赋值给dmg。 具体请看程序和注释。

三、程序

#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;
}

原文发布于微信公众号 - 海天一树(gh_de7b45c40e8b)

原文发表时间:2018-05-04

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏人工智能头条

Python 再牛,在字符串排序上还是被 Julia 和 R 碾压

在《实例对比 Julia, R, Python,谁是狼语言?》我们简单介绍了 Julia 的背景,以及通过优化一个似然函数的参数 μ 和 σ,来对比 Julia...

13930
来自专栏算法channel

动态规划:括号知多少

主要推送关于对算法的思考以及应用的消息。培养思维能力,注重过程,挖掘背后的原理,刨根问底。本着严谨和准确的态度,目标是撰写实用和启发性的文章,欢迎您的关注。 0...

37470
来自专栏小红豆的数据分析

小蛇学python(6)python实现经典排序算法并可视化分析复杂度

排序算法在算法界是一个怎么样的存在?就好像在学术界中数学的地位,说直接用好像用不上,可是不会做起事情来总会捉襟见肘,左支右绌。找工作的时候,有的面试官甚至会让我...

23120
来自专栏专注数据中心高性能网络技术研发

[LeetCode]HashTable主题系列{第3题}

1. 内容介绍 开一篇文章记录在leetcode中HashTable主题下面的题目和自己的思考以及优化过程,具体内容层次按照{题目,分析,初解,初解结果,优化解...

37490
来自专栏C语言及其他语言

[每日一题]偶数求和

题目描述 有一个长度为n(n<=100)的数列,该数列定义为从2开始的递增有序偶数(公差为2的等差数列),现在要求你按照顺序每m个数求出一个平均值,如果最后不足...

29750
来自专栏大数据文摘

正则表达式太慢?这里有一个提速100倍的方案(附代码)

27940
来自专栏追不上乌龟的兔子

[多少懂点位运算]找出唯一的数字

大家都知道现代计算机的底层是以二进制为基础的,计算机所有的操作最后都归结到了简单的二进制位运算上:与,或,非和异或。

27450
来自专栏xingoo, 一个梦想做发明家的程序员

大整数乘法

                                                                                ...

24450
来自专栏chenjx85的技术专栏

leetcode-169-Majority Element

21940
来自专栏C语言及其他语言

[每日一题]矩阵问题

今天给大家分享的是二维数组的基本用法,主要是利用数组对行列的控制 题目描述 求一个3×3矩阵对角线元素之和。 输入 矩阵 输出 主对角线 副对角线 元素和 ...

33770

扫码关注云+社区

领取腾讯云代金券