一个骚题目，自己真是naive，真是naive
http://codeforces.com/contest/1156/problem/C
俄罗斯英语看着真几把费劲。
本以为贪心就完了，但是却想当然了，这个题目得好好反思，做了两个题目排名900多？？？我服了。
假设我们已经有了一个最终的最优答案，那么有如下两个观察：
1.那么我们可以证明两对match的点(a,b)和(c,d)中，两者必然可以不嵌套，就是a<c<d<b。因为我们基于d-c>z那么必有d-a>z那么可以解这个嵌套的情况为(a,d)和(c,b)。
2.两对match的点(a,b)和(c,d)中，两者必然可以相交。因为如果a<b<c<d，容易证明(a,c)和(b,d)必然也是合法的。
很容易根据观察1想到滑动窗口是不？？？
naive！！！
因为:
滑动窗口的题目->答案不嵌套
答案不嵌套 ≠ 滑动窗口
两者不是充要的。行，今天长记性了！
反例：
n=4 z=2
arr= [ 1 , 3 , 4 , 5 ]
滑动窗口的话：1和3匹配完了，4和5匹配不了，于是只能成1对。
但是最优答案是(1,3),(3,5)
而观察2证明的匹配对必然相交让我们的右边界必须从数组的右半边来找。
为什么这么说呢？
所有窗口相交的意思是：最大的左边界<最小的右边界。也就是从小到大排一下，先全部是左，再全部是右。
那么完全可以平移那些右边界到数组的后半边，成为算法所构造的那个样子。于是得证，任一最优解必然对应着当前算法所找到的解。而当前算法在观察1,2的限制下是最优的贪心解，那么得证。
如果答案是n//2那么匹配的两边各来自左右半边才能符合观察2，对不？而且还是从小到大一一对应。
最好能用最优答案转换的方法证明这个结论是对的，因为现在还是不显然。