Tourist's Notes

Tourist's Notes

洛谷题目
郑航CoderOJ

首先一个很明显的思路就是，从每个输入的点开始，往两边遍历。但是要保证每次遍历不管从那边开始，最终都要相遇，且相遇时候相等或相差1。
所以用一个优先队列，每次从最小的开始遍历就可以了。
但是时间复杂度很高，为nlogn。而且n的数量级是10⁸,数组保存不下，所以空间复杂度爆了。

#include<bits/stdc++.h> 
using namespace std;
struct Node {int d, h;bool operator < (const Node b) const {return h > b.h;}
};
vector<int> v,w;
int main() {int n, m;scanf("%d%d", &n, &m);v.resize(n + 1);w.resize(n + 1);priority_queue<Node> q;while(m--) {int d, h;scanf("%d %d", &d, &h);w[d] = h;v[d] = 1;q.push({d, h});}int mx = 0, f = 1;while(!q.empty()) {Node t = q.top();q.pop();mx = max(mx, t.h);if(t.d - 1 > 0) {if(!v[t.d - 1]) {q.push({t.d - 1, t.h + 1});v[t.d - 1] = 1;w[t.d - 1] = t.h + 1;}else if(abs(w[t.d - 1] - w[t.d]) > 1) {f = 0;break;}}if(t.d + 1 <= n) {if(!v[t.d + 1]) {q.push({t.d + 1, t.h + 1});v[t.d + 1] = 1;w[t.d + 1] = t.h + 1;}else if(abs(w[t.d + 1] - w[t.d]) > 1) {f = 0;break;}}}if(f)cout << mx;elseputs("IMPOSSIBLE");return 0;
}

我们可以重新发现：

1. 两边高度差值和下标之差相等时，最大值只去两个高度的最大值；
2. 两边高度差小于下标之差时可以在中间某个位置取到最大值。我们可以假设中间某个位置的（h，d）对应为（c，z），两边两点分别为（a，x），（b，y），那么可以的出来两个式子 (c - a = z - x ), (b - c = y - z) ，联立得 c = （a + b + y - x）/ 2 。情况1也适应这个式子
3. 其他情况就是错误的

最后要注意，第一个输入点和最开始可能组成一个最大值，最后一个输入点和最后一个点可能组成最大值。

#include<bits/stdc++.h>
using namespace std;
int main() {int n, m, f = 1, mx = 0;scanf("%d %d", &n, &m);int pd, ph;scanf("%d %d", &pd, &ph);mx = max(mx, ph + pd - 1);while(--m) {int d, h;scanf("%d %d", &d, &h);if(abs(ph - h) > (d - pd)) f = 0;mx = max(mx, (ph + h + d - pd) / 2);pd = d, ph = h;}mx = max(mx, n - pd + ph);if(f) printf("%d", mx);else  puts("IMPOSSIBLE");return 0;
}