做钓鱼网站原理/怎么做一个网站页面

听戴牛讲完这题体会了排序不等式在贪心中的作用

这个题说的是后很多怪兽同时攻击一个游侠，怪兽有不同的血量和攻击力。游侠有一个攻击力，如果选择攻击怪兽的顺序使得游侠扣血最少

贪心构造：对于2只怪兽，A，B；假设当前怪兽总攻击值为V。

设怪兽A的攻击力，和被攻击次数（攻击多少次死亡） 为 GA,CA;

设怪兽B的攻击力，和被攻击次数（攻击多少次死亡） 为 GB,CB;

可知，如果先攻击怪兽A，后攻击怪兽B ，那么游侠的去血量分别为

正在杀怪兽A ：V *CA ，怪兽A死亡后，正在杀怪兽B ：(V-GA) * CB ；

杀完两只怪兽的去血总量为 SUM1 = V *CA + (V-GA) * CB;

同理，先攻击怪兽B，后攻击怪兽A ，SUM2 = V *CB + (V-GB) * CA;

我们知道，去血最少，即要取min （ SUM1，SUM2 );

令SUM1 < SUM2;

则  V *CA + (V-GA) * CB < V *CB + (V-GB) * CA

化简为 GB*CA < GA*CB

以此条件排序，贪心即可。

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
using namespace std;
struct point{int hp;int a;       
}mon[10005];
int m;
int cmp(const void * a,const void * b){struct point *aa=(struct point *)a;struct point *bb=(struct point *)b;return (int)ceil((double)aa->hp/m) * bb->a  -  aa->a * (int)ceil((double)bb->hp/m);
}
int main(){int t,T,i;int n;scanf("%d",&T);int ca=0;for(t=1;t<=T;t++){scanf("%d %d",&n,&m);for(i=1;i<=n;i++){scanf("%d %d",&mon[i].hp,&mon[i].a);                  }                  qsort(&mon[1],n,sizeof(mon[1]),cmp);__int64  sum=0,t=0;for(i=1;i<=n;i++){t+=(__int64 )ceil((double)mon[i].hp/(double)m);sum+=(__int64 )mon[i].a*t;                                                      }printf("Case #%d: ",++ca);printf("%I64d\n",sum);}
}