本文共 958 字，大约阅读时间需要 3 分钟。

题意：有N个敌人，每个敌人都有血条HP和伤害DPS，你的HP无限，伤害固定为1，而且你在攻击敌人的同时，所有HP不为0的敌人都能攻击你。求出击杀所有敌人所需的最小HP损失。

原题链接：

分析：此题跟Protecting The Flowers很相似，用类似的算法解决。

伪代码如下：

输入n sum=s=0; for(i=0;i<=n-1;i++) { scanf("%lf%lf",&d[i],&h[i]); //d[i]为伤害，h[i]为血条 v[i]=h[i]/d[i]; //v[i]为衡量哪个敌人先杀的权值，小的先杀，大的后杀，同flowers那道题一样 s+=d[i]; } sort(n); //选择排序即可 for(i=0;i<=n-1;i++) { sum+=s*h[i]; s-=d[i]; } 输出sum；

代码如下：

#include
   
    using namespace std;double h[25],d[25],v[25];void sort(int n){	int i,j,k;	for(i=0;i<=n-2;i++)	{		k=i;		for(j=i+1;j<=n-1;j++)		{			if(v[k]>v[j]) k=j;		}		if(k!=i)		{			double t;			t=v[i],v[i]=v[k];v[k]=t;			t=h[i];h[i]=h[k];h[k]=t;			t=d[i];d[i]=d[k];d[k]=t;		}//		printf("%.2lf %.2lf %.2lf\n",d[i],h[i],v[i]);	}}int main(){	int n,i;	long long sum,s;	while(~scanf("%d",&n))	{		sum=s=0;		for(i=0;i<=n-1;i++)		{			scanf("%lf %lf",&d[i],&h[i]);			v[i]=h[i]/d[i];			s+=d[i];		}		sort(n);		for(i=0;i<=n-1;i++)		{			sum+=s*h[i];			s-=d[i];		}		printf("%lld\n",sum);	}	return 0;}
   

转载地址：http://bfdci.baihongyu.com/