2018徐州icpc网络赛G题

这题看了bin巨的代码才恍然大悟。话不多说，先上一张图：

 

 

图中的1，2，3.代表1是最后的海浪，3是最一开始的海浪。我们把x轴,y轴分开讨论，先讨论x轴方向的，1因为是最上面的海浪，所以 ans=ans+len[1]。 然后看1下面的海浪2，明显海浪2有一段被海浪1截断了，所以 要用len2-len1。这里的len1怎么找呢？其实就是找一个在本层海浪上面的所有海浪里面，比海浪2的长度短，又最接近的数。我们这里可以把之前的海浪存一个set里面，set是自动升序的，st.lower_bound（本层海浪）一下,就可以求出截断的长度了， ans+=vec[本层]-len(最大截断长度)。

y方向的也一样，最后加起来就行了

lower_bound 不懂可以看 这里：点我~~

上bin巨代码：

#include <bits/stdc++.h>
#define Iter set<int>::iterator 
using namespace std;

long long gao(vector<int> vec) {
	int len = vec.size();
	set<int> st;
	long long ans = 0;
	for (int i = len-1; i >= 0; i--) {
		Iter it = st.lower_bound(vec[i]);
		if (it == st.begin()) {
			ans += vec[i];
		} else {
			it--;
			ans += vec[i] - *it;
		}
		st.insert(vec[i]);
	}
	return ans;
}
int main() {
	int n;
	while(scanf("%d", &n) == 1) {
		vector<int>vec1, vec2;
		int x,y;
		while(n--) {
			scanf("%d%d", &x, &y);
			vec1.push_back(x);
			vec2.push_back(y);
		}
		cout<<gao(vec1) + gao(vec2)<<endl;
	}
}