http://acm.hdu.edu.cn/showproblem.php?pid=3979

减弱版的题目

http://acm.hdu.edu.cn/showproblem.php?pid=4310

水题，在网上搜下是排序不等式，我也不知道什么叫排序不等式，如果深入的思考的话还是容易想出来的

这题肯定是贪心是肯定的，或者说是是排序把！但是 怪物A  为什么就在  怪物B 之前处理呢？

这样就把很多歌怪物化为A  和 B 两个怪物是先杀谁的问题。

如果前面耗费的时间我们设为cnt，那么如果按 A -> B的话，那么  花费的

  ans1+=  a.akh*(cnt+ a.time) + b.akh*(cnt+a.time+ b.time)

如果B -> A 的话，那么花费

  ans2+=b.akh*(cnt+b.time) +a.akh*(cnt+b.time+a.time)

如果ans1 < ans2  化简 :  a.tim*b.akh < b.tim*a.akh ,那么这就是排序的依据

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>using namespace std;struct Mon
{int kill,hp;int tim;
}mon[100010];int cmp(Mon a,Mon b)
{return a.tim*b.kill < b.tim*a.kill;
}
int main()
{int ca,cas=1,n,m;scanf("%d",&ca);while(ca--){scanf("%d%d",&n,&m);int a,b;for(int i=0;i<n;i++){scanf("%d%d",&a,&b);//cout<<a<<" "<<b<<endl;mon[i].kill=b,mon[i].hp=a;mon[i].tim=a/m+1-(a%m==0);}sort(mon,mon+n,cmp);// for(int i=0;i<n;i++)//    cout<<mon[i].kill<<" "<<mon[i].hp<<endl;long long cnt=0,ans=0;for(int i=0;i<n;i++){if(mon[i].hp%m==0){ans+=mon[i].kill*(cnt+mon[i].hp/m);cnt+=mon[i].hp/m;}else{ans+=mon[i].kill*(cnt+mon[i].hp/m+1);cnt+=mon[i].hp/m+1;}}printf("Case #%d: %I64d\n",cas++,ans);}return 0;
}