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;
	else
		puts("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;
}