【NOIP模拟】打膈膜

Description

Solution

一看就是一道贪心题。
而且贪心的策略实在，太明显了。
首先，群伤肯定在单伤的前面放完，然后在一个个用重击和轻击。
那么枚举一下用多少次群伤，然后模拟就好了。

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define fo(i,a,b) for(i=a;i<=b;i++)
#define fod(i,a,b) for(i=a;i>=b;i--)
using namespace std;
typedef long long ll;
const int maxn=100007;
ll i,j,k,l,t,n,m;
ll ans,ans1,ci,shu;
ll a[maxn],b[maxn];
int main(){
//  freopen("fan.in","r",stdin);freopen("game.in","r",stdin);freopen("game.out","w",stdout);scanf("%lld%lld",&n,&m);fo(i,1,n)scanf("%lld",&a[i]);sort(a+1,a+1+n);ans=99999999999999999;fo(t,0,m){ans1=0;fo(i,1,n){if(a[i]>t)b[i]=a[i]-t,ans1+=t;else b[i]=0,ans1+=a[i]-1;}j=m-t;fo(i,1,n){if(b[i]){k=min(j,b[i]/2);j-=k;k+=b[i]-k*2;ans1+=k*(n-i+1)-1;}}ans=min(ans,ans1);}printf("%lld\n",ans);
}