网易游戏8.11笔试洪水题优化思路
因为第三题浪费了点时间，第四题没什么时间做，直接Brute Force走了o(nq)的解法，毫无疑问只剩40%的AC率。。。
然后看时间不够，就懒得继续写了。
搞完之后想想优化思路，有以下一个优化思路，估计应该是最优解了。
建立一个辅助数据结构标注 高度，种类，下标。
种类分为水位：-1/尚未被淹的基站：0/被淹的基站:1
然后把基站和洪水放一起根据高度排序，记录当前基站集群的数量，初始为1。
然后从头遍历，每遇到一个洪水，遍历该洪水淹的基站。
若该基站左右的基站都尚未被淹，则集群数量+1；
若该基站左右的基站其中一个被淹，或本就是边缘基站，则集群数量不变；
若该基站左右的基站都已经被淹，则集群数量-1；
最后将计算完的集群数量放在数组里，对应该洪水的下标位置。
最后统一输出
种类分为水位：-1/尚未被淹的基站：0/被淹的基站:1
然后把基站和洪水放一起根据高度排序，记录当前基站集群的数量，初始为1。
然后从头遍历，每遇到一个洪水，遍历该洪水淹的基站。
若该基站左右的基站都尚未被淹，则集群数量+1；
若该基站左右的基站其中一个被淹，或本就是边缘基站，则集群数量不变；
若该基站左右的基站都已经被淹，则集群数量-1；
最后将计算完的集群数量放在数组里，对应该洪水的下标位置。
最后统一输出
时间复杂度：O((n+q)log(n+q))
-----
昂，有点无聊，贴一下代码吧。
#include <stdio.h>
#include <vector>
#include <algorithm>
#pragma warning(disable:4996)
using namespace std;
class Node{
public:
int h;
int type;
int idx;
Node(int h, int type, int idx):h(h),type(type),idx(idx) {}
};
int main() {
int n, q, y, group = 1;
scanf("%d", &n);
Node **base = new Node*[n];
for (int i = 0; i < n; ++i) {
scanf("%d", &y);
base[i] = new Node(y, 0, i);
}
scanf("%d", &q);
int size = n + q;
Node ** nodes = new Node*[size];
for (int i = 0; i < q; ++i) {
scanf("%d", &y);
nodes[i] = new Node(y, -1, i);
}
for (int i = 0; i < n; ++i) nodes[i + q] = base[i];
sort(nodes, nodes + n + q, [](Node* pre, Node* post) {return pre->h == post->h ? pre->type > post->type : pre->h < post->h;});
vector<Node*> vec;
int* res = new int[q];
for (int i = 0; i < size; ++i) {
switch (nodes[i]->type)
{
case -1:
for (Node* node : vec) {
int sink = 0;
if (node->idx == 0 || base[node->idx - 1]->type == 1) ++sink;
if (node->idx == n - 1 || base[node->idx + 1]->type == 1) ++sink;
group += (sink == 0 ? 1 : (sink == 1 ? 0 : -1));
node->type = 1;
}
res[nodes[i]->idx] = group;
vec.clear();
break;
case 0:
vec.push_back(nodes[i]);
break;
}
}
for_each(res, res + q, [](int v) {printf("%d\n", v); });
return 0;
}
/*
10
6 12 20 14 15 15 7 19 18 13
6
15 23 19 1 17 24
*/ 