优惠券
时间限制：1秒
空间限制：32768K
美团点评上有很多餐馆优惠券，用户可以在美团点评App上购买。每张优惠券有一个唯一的正整数编号。当用户在相应餐馆就餐时，可以在餐馆使用优惠券进行消费。优惠券的购买和使用按照时间顺序逐行记录在日志文件中，运营人员会定期抽查日志文件看业务是否正确。业务正确的定义为：一个优惠券必须先被购买，然后才能被使用。
某次抽查时，发现有硬盘故障，历史日志中有部分行损坏，这些行的存在是已知的，但是行的内容读不出来。假设损坏的行可以是任意的优惠券的购买或者使用。
现在问这次抽查中业务是否正确。若有错，输出最早出现错误的那一行，即求出最大s，使得记录1到s-1满足要求；若没有错误，输出-1。
输入描述:
1
2
3
4
5
6
7
8
9
10
11
| m 分别表示 m (1 ≤ m ≤ 5 * 10^5) 条记录。
下面有m行，格式为：
I x （I为Input的缩写，表示购买优惠券x）；
O x（O为Output的缩写，表示使用优惠券x）；
? （表示这条记录不知道）。
这里x为正整数，且x ≤ 10^5 。
|
输出描述:
1
| -1 或 x(1 ≤ x ≤ m) 其中x为使得1到x-1这些记录合法的最大行号。
|
输入例子:
1
2
3
4
5
6
7
8
9
10
11
12
13
| 0
1
O 1
2
？
O 1
3
I 1
？
O 1
2
I 2
O 1
|
输出例子:
有点坑，要考虑很多细节东西。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
| import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
public class T3优惠券 {
private static final Set Set = null;
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc=new Scanner(System.in);
while(sc.hasNext()){
int m=sc.nextInt();
int x=-1;
int[] input=new int[m];
int unknown=0;
boolean f=false;
for (int i = 0; i < m; i++) {
char c=sc.next().charAt(0);
if(c=='I'){
int k=sc.nextInt();
boolean falg=true;
for (int j = 0; j < input.length && f==false; j++) {
if(k==input[j]){
falg=false;
input[i]=-1;
break;
}else if(input[j]==0)
break;
}
if(falg)
input[i]=k;
}else if(c=='O'){
int k=sc.nextInt();
input[i]=-1;
boolean falg=true;
for (int j = 0; j < input.length && f==false; j++) {
if(k==input[j]){
input[j]=-1;
falg=false;
break;
}else if(input[j] == 0){
break;
}
}
if(falg && f==false){
if(unknown>0){
unknown--;
}else{
x=i+1;
f=true;
}
}
}else if(c=='?'){
input[i]=-1;
unknown++;
}
}
System.out.println(x);
}
}
}
|