理论上我代码应该是O(n), 为什么只过55% 剩余全部超时呢?
我想的是: 先把所有ID都列出来. 然后在读取的时候, 把第一条和最后一条留着最后处理, 中间所有打卡的ID都不可能是老板, 指教从list中移除
读取到最后一条后判断第一条和最后一条: 1. 如果两个ID相同, 则老板可能是这个. 2. 如果ID不同, 第二位数也不同(0和1). 则老板也不可能是. 3. ID不同, 第二位数都是(1), 则排除第一位. 4. ID不同, 第二位都是(0), 则直接排除最后一个.
难道是还有情况没有考虑到吗? 求指教. 感谢
public static void main(String args[]){
Scanner scan = new Scanner(System.in);
String[] temp = scan.nextLine().split(" ");
int n = Integer.parseInt(temp[0]);
int m = Integer.parseInt(temp[1]);
List<Integer> possible = new ArrayList<>();
for(int a = 0; a < n; a++) {
possible.add(a+1);
}
int count = 0;
int[] first = new int[2];
while(count < m){
temp = scan.nextLine().split(" ");
if(count == 0) {
first[0] = Integer.parseInt(temp[0]);
first[1] = Integer.parseInt(temp[1]);
count++;
continue;
}
if(count == m-1) {
if(first[1] == Integer.parseInt(temp[1])) {
if(first[1] == 0) possible.remove(new Integer(first[0]));
else possible.remove(new Integer(Integer.parseInt(temp[0])));
}else {
if(first[0] != Integer.parseInt(temp[0])) {
possible.remove(new Integer(Integer.parseInt(temp[0])));
possible.remove(new Integer(first[0]));
}
}
break;
}
possible.remove(new Integer(Integer.parseInt(temp[0])));
count++;
}
for(Integer a: possible) System.out.print(a+" ");
} 
全部评论
(0) 回帖