CF1253B - Silly Mistake（源地址自⇔CF1253B）
目录Problem
tag：
⇔贪心、⇔构造性算法、⇔提高级（*1400）
题意：
（简化版）对于给定的序列，要求将其分成满足条件的若干段，条件如下：
- 如果在这一段中有 \(k\) ，则一定要有 \(-k\) 。
输出分段的数量及每一段的元素数量；若不能恰好分割完，输出 \(-1\) 。
思路：
（队内赛自己， \(\mathcal O (n* log_2 n)\) ）寻找某一元素在此前有没有出现过，容易想到二分查找，能用二分查找的容器必然是有序的，这里选用 std::set 。分三种情况讨论：
-
读入正数 \(x\) ——若 \(x\) 不在容器中、 \(x\) 在这一分段里尚未出现过（未被标记），则将 \(x\) 加入容器。
-
读入负数 \(-x\) ——若 \(x\) 已在容器中，则删除 \(x\) 。
-
其他所有情况均不满足条件。
每次容器为空时，即代表一个分段，记录并将标记数组清空。
（官方，\(\mathcal O(n)\) ）优化二分查找为数组直接记录，优化标记数组为 std::map （因为涉及到多次清空操作，普通数组不能胜任该工作）即可。
使用变量 len 记录分段所含元素的数量，当其为 \(0\) 时，即代表一个分段。
AC代码1（队内赛自己）：
//A WIDA Project
#include <bits/stdc++.h>
using namespace std;
#define LL long long
LL n, num[1000050], x, pre;
bool Ans = true;
vector<int> ans;
set<int> s, v;
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i ++) {
cin >> x;
if(x > 0) {
if(s.find(x) == s.end() && v.find(x) == v.end()) //里面没有 && 第一次放入
s.emplace(x), v.emplace(x);
else
Ans = false;
}else {
if(x < 0 && v.find(-x) != v.end()) //负数，里面有
s.erase(-x);
else
Ans = false;
}
if(s.empty()) {
v.clear();
ans.push_back(i - pre);
pre = i;
}
}
if(Ans == false || (int)ans.size() == 0 || !s.empty())
cout << "-1\n";
else {
cout << ans.size() << "\n";
for(auto i : ans)
cout << i << " ";
}
return 0;
}
AC代码2（官方思路，伪代码）
LL n, ans, num[MAX], x, pre, len, s[MAX];
bool Ans = true;
vector<int> ans;
map<int, int> v;
int main() {
cin >> n;
FOR(i, 1, n) {
cin >> x;
if(x > 0) {
if(s[x] == 0 && v[x] == 0)
s[x] ++, v[x] ++, len ++;
else
Ans = false;
}else {
if(s[-x] == 1)
s[-x] --, len --;
else
Ans = false;
}
if(len == 0) {
v.clear();
ans.push_back(i - pre);
pre = i;
}
}
if(Ans == false || sz(ans) == 0 || len != 0)
P(-1);
else {
P(ans.size());
For(i, ans)
cout << i << " ";
}
return 0;
}
错误次数
（补题1）忘记判断结束时容器是否为空，若有数据则也是 \(-1\) 。WA。
文 / WIDA
2021.12.20 成文
首发于WIDA个人博客，仅供学习讨论
更新日记：
2021.12.20 成文