#C240130B. 刷野I
前言(Front talk)
非常好题目,使我时间花费。
网址(Website)
题目详情 - 刷野I - Super
题解 - 刷野I - Super
题解(Solution)
很明显,先将怪物的血量排序,从小打到大最后一定是最优的。整体的思路是从结果推来的,我们先用最朴素的普通攻击计算伤害,然后再计算操作1和操作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;
}