原题: http://acm.nyist.net/JudgeOnline/problem.php?pid=1309
//nyoj 1309 特别难的贪心(看了大神的解题报告,看了好多次才明白) //1.对技能处理:把每项技能转化为两个值，一个是对神龙sl的伤害，一个是对冰法斗士zz的伤害 //2.有两种情况zz是必赢，①有一个技能满足 冰冻时间fz>=冷却时间cd 且 此技能伤害d>0,则sl必死 // ②有一个技能满足 冰冻时间fz-2>=冷却时间cd 且存在某一个技能的d>0，则sl也必死 //3.如果两种必赢情况都不满足,则只能用贪心来选择技能，尽量让sl先死 // ①把每个技能按 神龙的伤害 和 zz伤害之比(sl/zz) 排序，从高到低 // ②排序后，每次选择zz的血量hp范围内，效率最高的技能来杀神龙 // 直到最后，每一个技能都杀不死神龙,那zz就只能失败NO了。 // 一旦过程中有一个技能可以杀死神龙，break跳出，宣告zz胜利YES。 //注意：每次使用技能，神龙总是先受到伤害。而且每个技能的发射速度都是瞬间的！ //贪心思想体现在，每次选取在zz血量范围内效率最高的技能。 //这题我不会，考虑的细节不够，而且贪心想法也错,看完大神的解题报告深有感悟，果然自己水平还是太低。 #include<iostream> #include<cstdio> #include<algorithm> #include<math.h> #include<stdlib.h> #include<memory.h> #include<set> using namespace std; struct J { int sl; int zz; }j[1000001]; int cmp(const void *aa,const void*bb)//把效率高的排前面 { J a=*(J*)aa; J b=*(J*)bb; return a.sl*b.zz<a.zz*b.sl; } int main() { int t; scanf("%d",&t); while(t--) { int HP,D; int hp,n; scanf("%d %d",&HP,&D); scanf("%d %d",&hp,&n); int flag1=0; //0表示刚刚出现j[i].sl>0 int flag2=0; int flag3=0; for(int i=0;i<n;i++) { int d,fz,cd; scanf("%d %d %d",&d,&fz,&cd); if(fz>=cd && d>0) { flag1=1; } if(fz>cd){ flag2=1; } if(d>0){ flag3=1; } j[i].sl=d; j[i].zz=D*(cd-fz); } if(flag1|| flag2&&flag3) { printf("YES\n"); }else{ qsort(j,n,sizeof(j[0]),cmp); int i; while(HP>0) { for(i=0;i<n;i++)//遍历每一个技能 { if(j[i].sl==0)continue; if(j[i].sl>=HP){//如果这个技能可以一刀kill神龙，break跳出 HP=0; break; } if(j[i].zz<hp){ //选取自己血量范围内效率最高的技能。 HP-=j[i].sl; hp-=j[i].zz; break; } } if(i==n){ //没有一个技能可以杀死神龙 break; } } if(HP==0){ printf("YES\n"); }else{ printf("NO\n"); } } } return 0; }
