https://bbs.csdn.net/topics/392711132
系统提供的部分:
输入n和nxn的数据(0或1),转换成good[i][j]保存。
判断函数better(a,b),实际返回good[a][b]。
判断大佬的依据: 如果a为大佬,则对所有1 <= i <= n 且 a!=i, 有better[a,i] = 1, 且 better[i,a] = 0。
解决思路:
用一个n维数组x,标记n个人是否可能为大佬,初始化为x[i]=1. 后续计算中如果x[i] = 0则表示不可能是大佬。
a从1到n循环,i从1到n循环,当a!=i时,读取better[a,i]和better[i,a],如果不符合,则标记a不是大佬,并中断循环。
优化:每次读取better[a,i]之后,如果 = 1, 则标记x[i] = 0; 如果better[a,i] = 0,则标记 x[a] = 0;相应地,对每个a,先判断x[a]是否为0,如果为x[a]=0则直接跳过i的循环。