题目

分析

贪心，

先将怪物按生命值从小到大排序（显然按这个顺序打是最优的）

枚举可以发对少次群体攻击，

首先将所有的群体攻击发出去，

然后一个一个怪物打，当当前怪物生命值大于2，如果还有魔法值就放重击，

其余情况普通攻击。

#include <cmath>

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <queue>

const long long maxlongint=2147483647;

const int mo=1000000007;

const int N=100005;

using namespace std;

long long a[N],n,m,ans,b[N],num;

int main()

{

	scanf("%lld%lld",&n,&m);

	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);

	num=maxlongint*10000000;

	sort(a+1,a+1+n);

	for(int i=0;i<=m;i++)

	{

		ans=0;

		for(int j=1;j<=n;j++)

		{

			b[j]=a[j]-i;

			if(b[j]>0) ans+=i;

				else ans+=a[j]-1;

		}

		int j=m-i;

		for(int k=1;k<=n;k++)

			if(b[k])

			{

				while(j && b[k]>1)

				{

					j--;

					if(b[k]==2)

					{

						ans+=n-k;

					}

					else

						ans+=n-k+1;

					b[k]-=2;

				}

				if(b[k]>0)

					ans+=(n-k+1)*(b[k]-1)+n-k;

			}

		num=min(ans,num);

	}

	printf("%lld",num);

}

巴特西

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

题目

分析

最新文章

热门文章