HDU6669（贪心

刚开始看错题，一通乱搞发现了按输入顺序遍历。

参考了下大佬的博客，发现了如果区间有交集那么就不断取他们共同的区间，如果没有交集那么就计算区间到区间之间的最小距离。乱搞一通会发现要么全走2，要么n-1次2加一次1，所以我们需要纠结的就是这最后一次到底怎么走。

首先如果我们到这个区间的最短距离是奇数且这个区间长度大于1，那么说明可以走个1，但是我们还得为之后的区间考虑。

比如我们从点1 走到A区间[4,5]。 A区间[4,5]之后的下一个区间是B区间[7,8]

从1走2+1到4，从4到7得走2+1两次，共4次

但是从1走2+2到5，从5到7只要走一个，共3次

因此我们确定下端点的具***置即可

这里比较巧妙的是可以不必手动确定我们当前的所在位置，一切由区间交集决定最优位置

#include<cstdio>
#include<iostream> 
#include<algorithm>

using namespace std;

const int Max = 1000000;
int le, ri;
int T, n, res;

int step(int l, int r){
	int l1 = max(l, le);
	int r1 = min(r, ri);
	
	//一直不断地缩小交集,卡完了所有交集 
	if(l1 <= r1){
		le = l1;
		ri = r1;
		return 0;
	}
	
	int ans;
	//新的区间在原区间的左边 
	if(r < le){
		ans = (le - r + 1) / 2;
		//ans = (le - r) % 2 + (le - r) / 2; 
		ri = r;
		
		//如果需要走一次1步且区间本身大小就>1，那么将区间大小置为2。 
		if((le - r) % 2 == 1 && l != r) le = r - 1;
		//否则就置为1 
		else le = r;
	}
	
	else {
		ans = (l - ri + 1) / 2;
		le = l;
		
		if((l - ri) % 2 == 1 && l != r) ri = l + 1;
		else ri = l;
	}
	
	return ans;
} 

int main()
{
	scanf("%d", &T);
	
	while(T--){
		le = 1, ri = Max, res = 0;
		scanf("%d", &n);
		
		for(int i = 1; i <= n; i++){
			int a, b;
			scanf("%d%d", &a, &b);
			
			res += step(a, b);
		}
		printf("%d\n", res);
	}
	
	return 0;
}