算法
(数据结构) $O(m\log m)$
可以先用 map
来维护一下每一行所在的黑色棋子的列坐标,然后通过 set
来维护白色棋子所有可能的列坐标,然后从上到下从左到右的顺序遍历所有的黑色棋子。
对于每一个黑色棋子,当且仅当在左边一列或右边一列上存在白色棋子,则可以把这个白色棋子移到这个黑色棋子的位置;若黑色棋子正上方存在白色棋子的话,直接把这个列坐标从 $set$ 中删去即可。
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::map;
using std::set;
using std::vector;
int main() {
int n, m;
cin >> n >> m;
map<int, vector<int>> mp;
rep(i, m) {
int x, y;
cin >> x >> y;
mp[x].push_back(y);
}
set<int> s;
s.insert(n);
for (auto p : mp) {
vector<int> add;
for (int y : p.second) {
if (s.count(y - 1) or s.count(y + 1)) add.push_back(y);
}
for (int y : p.second) s.erase(y);
for (int y : add) s.insert(y);
}
cout << s.size() << '\n';
return 0;
}