JZOJ 4821. 【NOIP2016提高A组模拟10.15】打膈膜

Problem

Description

Input

Output

Sample Input
样例输入1：
2 1
2 1
样例输入2：
3 4
2 4 4
Sample Output
样例输出1：
1
样例输出2：
6
Data Constraint

Solution

一般人都会想到DP，而我们想到了一个更加容易AC的贪心方法。
我们先把生命从小到大排好序，然后依次去打，如果当前怪的生命值为 1 或场上怪物数量>2，一定要放群攻，否则放重击。如果m=0就一个个打。

Code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<cstring>
#define N 100005
#define LL long long
#define fo(i,a,b) for(i=a;i<=b;i++)
using namespace std;
LL n,m,i,j,k,last,p,xl,ans,h[N],f[N][105];
int main()
{scanf("%lld%lld",&n,&m);fo(i,1,n) scanf("%lld",&h[i]);sort(h+1,h+n+1);last=n;fo(i,1,n)if (h[i]){if (m){if (last>2){xl=min(h[i],m);LL L=last;ans+=last*(xl-1);fo(j,i,n){h[j]-=xl;if (!h[j]) L--;}m-=xl;ans+=L;last=L;} else{while (h[i]>1 && m){h[i]-=2;if (!h[i]) last--;m--;ans+=last;}if (h[i]==1 || last>2){xl=min(h[i],m);fo(j,i,n){h[j]-=xl;if (!h[j]) last--;}m-=xl;ans+=last;}}}if (h[i]){ans+=h[i]*last-1;last--;}}printf("%lld",ans);
}