@[fzj2007](/user/172370) 因为数据中实际上保证了操作 3 序列中必定存在 x
by lcyxds @ 2021-04-06 12:32:03
@[fzj2007](/user/172370) 我的 AC 代码:
```cpp
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int n;
vector<int> bst;
int main() {
int opt, x;
// freopen("vector.in", "r", stdin);
cin >> n;
while (n--) {
cin >> opt >> x;
switch(opt) {
case 1:
bst.insert(lower_bound(bst.begin(), bst.end(), x), x);
break;
case 2:
bst.erase(lower_bound(bst.begin(), bst.end(), x));
break;
case 3:
cout << lower_bound(bst.begin(), bst.end(), x)-bst.begin()+1 << endl;
break;
case 4:
cout << bst[x-1] << endl;
break;
case 5:
cout << *(lower_bound(bst.begin(), bst.end(), x)-1) << endl;
break;
case 6:
cout << *upper_bound(bst.begin(), bst.end(), x) << endl;
break;
}
}
// fclose(stdin);
return 0;
}
```
在操作 3 中添加断点:
```cpp
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int n;
vector<int> bst;
int main() {
int opt, x, t;
// freopen("vector.in", "r", stdin);
cin >> n;
while (n--) {
cin >> opt >> x;
switch(opt) {
case 1:
bst.insert(lower_bound(bst.begin(), bst.end(), x), x);
break;
case 2:
bst.erase(lower_bound(bst.begin(), bst.end(), x));
break;
case 3:
t = lower_bound(bst.begin(), bst.end(), x)-bst.begin();
if (bst[t]!=x) return 1;
cout << t+1 << endl;
break;
case 4:
cout << bst[x-1] << endl;
break;
case 5:
cout << *(lower_bound(bst.begin(), bst.end(), x)-1) << endl;
break;
case 6:
cout << *upper_bound(bst.begin(), bst.end(), x) << endl;
break;
}
}
// fclose(stdin);
return 0;
}
```
仍然可 AC 此题。
by lcyxds @ 2021-04-06 12:36:25
另外不要讨论这个代码的算法复杂度,本来就是 n 方,这个不是重点
主要是暴力代码添加断点要简单的多
by lcyxds @ 2021-04-06 12:38:45
@[lcyxds](/user/124314) 本题并没有保证一定存在,所以可以加hack数据(
by fzj2007 @ 2021-04-06 13:34:45
@[fzj2007](/user/172370) 没意义
by lcyxds @ 2021-04-06 13:50:37
@[lcyxds](/user/124314) 有意义,对于那些错误的写法在考场上就会被卡
by fzj2007 @ 2021-04-06 13:52:22
@[fzj2007](/user/172370) 考场上不会考板子而且这种东西一定会强调的
by lcyxds @ 2021-04-06 13:53:32