{题解}[jzoj4821]【NOIP2016提高A组模拟10.15】打膈膜

本文主要是介绍{题解}[jzoj4821]【NOIP2016提高A组模拟10.15】打膈膜，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门

Description

你可以用<炉石>的模型进行理解
现在你手中有m张牌
每个回合有且仅有2点法力水晶
而且你是法师麦迪文

现对面场上有n只随从，都是1攻H_i血的
而你手中的牌只有魔爆术或寒冰箭(不知为何只能打2且失去冻结)
你作为一名冰法有好多好多(可理解做无限)盾！
问至少会被打掉多少盾

Analysis

贪心？贪心！就是贪心。
根据<炉石>的模型先瞎扯一下…
显然的，如果只考虑对所有随从的总伤害，必定是优先发AOE。

玩过<炉石>的都看得出来贪心策略！

好的，现在尝试证明：
比较显然的，优先用手上的牌(消耗法力)，没有牌了再使用英雄技能(普通攻击)。

Ⅰ 若当前怪生命值为1，(AOE不劣于火冲)优于猛击
猛击显然没有必要。
根据之前的
这便是显然的了。
为什么说是不劣于呢？
简单的例子: 一只1血，一只2血。

Ⅱ 若不止两个怪（施工中….）

Code

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const long long N = 101000, M = 110, H = 101000;
long long n,m;
long long a[N];
int main()
{freopen("game.in","r",stdin);freopen("game.out","w",stdout);scanf("%lld%lld", &n, &m);for (long long i = 1;i <= n;i ++){scanf("%lld", &a[i]);}sort(a + 1,a + 1 + n);long long i = 1, tot0 = 0;long long ans = 0;while (i <= n){if (m -- > 0){if ((a[i] - tot0 == 1) || ((n - i + 1) > 2)){tot0 ++;}else{a[i] -= 2;}}else{for (int j = i;j <= n;j ++){ans += ((a[j] - tot0) * (n - j + 1) - 1);}printf("%lld", ans);return 0;}while (((a[i] - tot0) <= 0)&& (i <= n)) i ++;ans += n - i + 1;}printf("%lld", ans);
}