发布时间: 2017年7月9日 20:20 最后更新: 2017年7月10日 21:11 时间限制: 2000ms 内存限制: 128M
描述最近，盛大计划开发一款手游，以下是简化版。系统和我方各有 n 头怪兽，每一头怪兽都有生命值和攻击力，并且当怪兽A攻击怪兽B，如果怪兽B的生命值高于怪兽A的攻击力，则怪兽B的生命力减少A的攻击力的数值，否则怪兽B将死亡。我方已经通过一些手段得知了系统怪兽的出战序列，我方想要知道，我方是否可以合理安排怪兽的出战序列，保证当系统的 n 头怪兽全部死亡时，而我方至少还存在一头怪兽。
所有怪兽是每秒攻击一次，即如果A和B战斗，A受到B的伤害的同时，B也受到A的伤害，直到一方死亡，换序列中的下一个怪兽，继续战斗。
输入第一行一个整数 T ，表示测试组数。 对于每组数据，第一行输入一个整数 n ， 1<=n<=10 , 表示怪兽的数目。 接下来 n 行，表示系统 n 头怪兽的出战序列，每一行两个整数 v , a , 1<=v<=1000 , 1<=a<=100 . 其中 v 表示生命值， a 表示攻击力。 接下来 n 行，表示我方 n 头怪兽，但是出战序列可以由我方自己安排。每行两个整数，含义类似。
输出每组数据输出一行。如果我方可以通过合理安排怪兽的出战序列，保证当系统的 n 头怪兽全部死亡，而我方至少还存在一头怪兽，那么输出YES；否则输出NO
样例输入1 复制 2 2 5 4 4 3 3 2 5 4 2 5 4 4 3 3 2 5 5 样例输出1 NO YES 选择语言 想法： 学会next_permutation函数（全排列） 代码： #include<bits/stdc++.h> using namespace std; const int maxn= 15; int order[maxn]= {0,1,2,3,4,5,6,7,8,9}; //出场顺序 int blood1[maxn],blood2[maxn]; int cost1[maxn],cost2[maxn]; int temp1[maxn],temp2[maxn]; int n,flag; bool judge(int order[]) { for(int i=0; i<n; i++) //由于每次都要改变blood的值，所以要注意初始化 { blood1[i]=temp1[i]; blood2[i]=temp2[i]; } int i=0,j=0; while(i<n&&j<n) { int xx=min(blood1[i]/cost2[order[j]],blood2[order[j]]/cost1[i]); //优化，减少循环次数 blood1[i]-=(cost2[order[j]]*xx); blood2[order[j]]-=(cost1[i]*xx); while(blood1[i]>0&&blood2[order[j]]>0) { blood1[i]-=cost2[order[j]]; blood2[order[j]]-=cost1[i]; } if(blood1[i]<=0) { i++; } if(blood2[order[j]]<=0) { j++; } } if(i==n&&j<n) flag=1; //系统的怪兽死完了，但我方还有怪兽存活 return flag; } int main() { int T; scanf("%d",&T); while(T--) { scanf("%d",&n); for(int i=0; i<n; i++) { scanf("%d%d",&blood1[i],&cost1[i]); temp1[i]=blood1[i]; } for(int i=0; i<n; i++) { scanf("%d%d",&blood2[i],&cost2[i]); temp2[i]=blood2[i]; } flag=0; do { if(judge(order)) { flag=1; break; } } while(next_permutation(order,order+n)); //全排列 if(flag) puts("YES"); else puts("NO"); } return 0; }