Coderforces B.Balanced Fighters

题目链接：https://codeforces.com/gym/102365/problem/B

Problem A. Balanced Fighters Examples

standard input

5 TheStrong 90 60 10 TheInvincible 10000 10000 10000 TheTough 70 50 25 TheBrick 3 1 4159 TheResilient 160 40 10

standard output

1 TheResilient TheStrong TheTough

standard input

1 TheLonely 500 500 500

standard output

0

分析 这道题目是要从输入的fighters中找出所有满足A赢B，B赢C，C赢A（也可以是A输B，B输C，C输A）的组合，基本思路是用一个二维数组存放所有fighters之间相互战斗输赢的结果，再用三重循环遍历这个二维数组，找出所有满足要求的三个fighters的组合并存起来，最后输出。

AC代码

#include <iostream> #include <cstdio> using namespace std; struct Fighters{ char name[20]; int HP; int AT; int DF; }a[105]; int b[105][105]; //存放1v1战斗结果 int ans[1000005][3]; //存放满足要求的组合 int fight(int i,int j) //1代表胜利，0代表平局，-1代表失败 { if(i==j) return 0; int p=max(0,a[j].AT-a[i].DF); int q=max(0,a[i].AT-a[j].DF); if(p==0&&q==0) return 0; else if(p==0&&q!=0) return 1; else if(p!=0&&q==0) return -1; else { int x=a[i].HP; int y=a[j].HP; while(x>0&&y>0) { x-=p; y-=q; } if(x>0&&y<=0) return 1; else if(x<=0&&y>0) return -1; else return 0; } } int main() { int cnt=0; int n,i,j,k; cin>>n; for(i=1;i<=n;i++) { cin>>a[i].name>>a[i].HP>>a[i].AT>>a[i].DF; } for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { b[i][j]=fight(i,j); } } for(i=1;i<=n-2;i++) { for(j=i+1;j<=n-1;j++) { for(k=j+1;k<=n;k++) { if(b[i][j]==1&&b[j][k]==1&&b[k][i]==1||b[i][j]==-1&&b[j][k]==-1&&b[k][i]==-1) { cnt++; ans[cnt][0]=i,ans[cnt][1]=j,ans[cnt][2]=k; } } } } cout<<cnt<<endl; for(i=1;i<=cnt;i++) { cout<<a[ans[i][0]].name<<" "<<a[ans[i][1]].name<<" "<<a[ans[i][2]].name<<endl; } return 0; }

注意 1.最后输出的名字的顺序可以是任意的，只要这三个fighters满足要求即可 2.在fight函数中要注意判断p，q是0的情况，否则可能陷入死循环 3.在存放战斗结果的b数组中，i，j都是从1开始遍历，虽然理论上知道i和j的战斗结果，j和i的战斗结果也就知道了，但是在三层for循环中，需要判断b[k][i]的结果,而k是比i大的，也就是说在b数组中，j不能从i+1开始遍历，而要从1开始遍历