hdu6669 Game【贪心】【2019百度之星初赛一 B题】

题意：

给你n个任务区间 $[a_i,b_i]$[ai​,bi​]， $1\le a_i\le b_i\le 1000000$1≤ai​≤bi​≤1000000
你可以选择起点，每次你可以 向左 走一步或者两步，或者向右走两步或一步
请你依次到达所有的区间，最少需要多少次

思路：

比赛的时候看错两次题，第一次没有看到依次，比赛过程中看到了，把排序贪心改掉了，但是还是看错了题，我一直以为是只能向左一步和向右两步…
参考博客
我看到好多博客都是直接先合并所有重合的区间，然后再进行移动算次数，这种写法明显不对，但是数据太水，居然给过了
hack数据如下

4
1 2
4 5
5 6
10 10

答案应该为4，但是如果提前合并了区间，答案就为5

我的思路为：
用两个数字l, r，代表每一次执行任务前我的点在区间 $[l,r]$[l,r]之间,由于起点可以随意起，于是我初始化为l = 1, r = 1000000,每次加入新的任务区间，更新当前点所在的区间，已经加入到这个区间的最短距离
1.如果有重合的部分就直接取重合的部分，不用移动
2.如果不重合，判断该区间与任务区间的距离为偶数则直接到达任务区间的端点最优，如果为奇数，那我们走一样的步数可以到达任务区间的的端点和相邻的点，则将区间更新为任务区间的端点和其相邻的点(建立在下一个任务区间长度大于1的前提下)

为什么我们要直接记录点的区间到不能直接取任务区间的端点作为到达的终点，因为如果存在当前区间与下一个任务区间长度为奇数，而我们用同样的步数可以到达两个终点，但是我们如果选择任务区间的端点来作为终点，如果下下任务区间与该端点的距离为奇数且比下下任务区间与该端点的相邻点的距离的大的话就不是最优的

#include<bits/stdc++.h>
using namespace std;
int l, r;
int solve(int x, int y) {
	int ll = max(x, l);
	int rr = min(y, r);
	if(ll <= rr) {
		l = ll;
		r = rr;
		return 0;
	}
	int res;
	if(y < l) { //新的任务区间在左边
		res =  (l - y + 1) / 2;
		r = y;
		if((l - y) % 2 == 1 && x != y) {
			l = y - 1;
		} else {
			l = y;
		}
	} else {//新的任务区间在右边
		res = (x - r + 1) / 2;
		l = x;
		if((x - r) % 2 == 1 && x != y) {
			r = x + 1;
		} else {
			r = x;
		}
	}
	return res;
}
int main() {
	int t, n, x, y;
	cin>>t;
	while(t--) {
		cin>>n;
		int ans = 0;
		l = 1, r = 1000000;
		while(n--) {
			cin>>x>>y;
			ans += solve(x, y);
		}
		cout<<ans<<endl;
	}
	return 0;
}