#C240130A. 刷野I

#C240130B. 刷野I

标签（Label）

• 思维

前言（Front talk)

$\qquad$非常好题目，使我时间花费。

网址（Website）

$\qquad$ 题目详情 - 刷野I - Super

$\qquad$ 题解 - 刷野I - Super

题解（Solution）

$\qquad$ 很明显，先将怪物的血量排序，从小打到大最后一定是最优的。整体的思路是从结果推来的，我们先用最朴素的普通攻击计算伤害，然后再计算操作1和操作2对答案的贡献即可。

$\qquad$ 对于操作一，总共要花费的血量为：$\sum_{i=1}^{n}(n-i+1)*a[i]$

$\qquad$ 对于操作二，每次肯定不会用操作二来打只有一滴血的怪，所以至少要打两滴血及以上的，相较于普通攻击来说会让当前幸存的怪物少打一轮，贡献为：$(n-i+1)$

$\qquad$ 对于操作三，贡献为让每一个幸存的怪物都少打一次，第 $i$ 个怪物掉一滴血贡献为 $(n-i+1)$ ，第 $i+1$ 个的贡献为 $n-(i+1)+1$ 。。。以此类推，可以得到等差数列，直接求和可得操作三的贡献为： $(n-l+i)*(n-l)/2$。

代码（Code）

#include<bits/stdc++.h>
#include<vector>
#include<queue>
#include<set>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define int long long
inline int input(){int x;return cin>>x,x;}
const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 101234;

int n,m,ans,a[N];
void Solve(){
	For(i,1,n) ans+=(n-i+1)*a[i];
	ans-=n;//打死怪物不需要扣血
	int l=1,d=0;//d:放的三技能个数 
	while(m && l<=n){
		if(a[l]-d<=0){l++;continue;}
		if(a[l]-d==1){
			if(n-l>=1){//如果不是最后一个 
				ans-=(n-l+1)*(n-l)/2;
				d++;
				m--;
			}else l++;//最后一个1血怪直接普攻打死 
		}else{
			int res1=0,res2=0;
			if(n-l>=2){//如果至少有三个怪物，用3技能才更优 
				ans-=(n-l+1)*(n-l)/2;
				d++;
				m--; 
			}else{
				ans-=n-l+1;
				a[l]-=2;
				m--;
			}
		}
	}return cout<<ans<<'\n',void();
}

signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	string str("jungle");
	freopen((str+".in").c_str(),"r",stdin);
	freopen((str+".out").c_str(),"w",stdout);
	cin>>n>>m;For(i,1,n) a[i]=input();
	int Tim=clock();
	sort(a+1,a+n+1);Solve();
	return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}