Problem Description

度度熊在玩一个好玩的游戏。 
游戏的主人公站在一根数轴上，他可以在数轴上任意移动，对于每次移动，他可以选择往左或往右走一格或两格。 
现在他要依次完成 n 个任务，对于任务 i，只要他处于区间 [ai,bi] 上，就算完成了任务。 
度度熊想知道，为了完成所有的任务，最少需要移动多少次？ 
度度熊可以任意选择初始位置。

Input

第一行一个整数 T  (1≤T≤10) 表示数据组数。 
对于每组数据，第一行一个整数 n (1≤n≤1000) 表示任务数。 
接下来 n 行，第 i 行两个整数 ai,bi (1≤ai≤bi≤1000000) 表示任务对应的区间

Output

对于每组数据，一行一个整数表示答案。

Sample Input

1
2
1 10
20 30

Sample Output

5

思路：

由于要依次完成 n 个任务，因此只需要考虑第 i 个区间与第 i+1 个区间的范围，若第 i 次任务与第 i+1 次任务有交集，那么选择重合部分就可以完成两个任务，这样再考虑重合区间跟第 i+2 个区间的范围，直到两相邻区间没有交集

当第 i 个任务与第 i+1 个任务没有交集时，判断当前任务 i 的所在区域是在第 i+1 个任务所在区域的左边还是右边来决定从哪个方向出发

由于每次可以走 2 步或者 1 步，可以看出无论两区间相差奇数个还是偶数个都是相同的，只是到达的位置不同，即相差偶数步时，走偶数次 2 即可到达；相差奇数步时，走偶数次 2 再走一个 1 即可到达

Source Program

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<utility> #include<stack> #include<queue> #include<vector> #include<set> #include<map> #include<bitset> #define EPS 1e-9 #define PI acos(-1.0) #define INF 0x3f3f3f3f #define leftleft long long #define Pair pair<int,int> const int MOD = 1E9+7; const int N = 1000+5; const int dx[] = {0,0,-1,1,-1,-1,1,1}; const int dy[] = {-1,1,0,0,-1,1,-1,1}; using namespace std;struct Node {int l,r; }a[N]; int main() {int t;scanf("%d",&t);while(t--) {int n;scanf("%d",&n);for(int i=1; i<=n; i++)scanf("%d%d",&a[i].l,&a[i].r);int res=0;int left=a[1].l,right=a[1].r;//当前区间for(int i=2; i<=n; i++) {int start=max(left, a[i].l);//重合区间左端点int endd=min(right, a[i].r);//重合区间右端点if(start<=endd) {//重合区间存在left=start;//更新当前区间左端点right=endd;//更新当前区间右端点continue;}else {//重合区间不存在if(a[i].l==a[i].r) {//区间为一个点时res+=min((abs(a[i].l-left)+1)/2,(abs(a[i].r-right)+1)/2);left=a[i].l;right=a[i].r;}else if(a[i].r<left) { //下一个区间在当前区间左端if((left-a[i].r)&1) {//两区间距离为奇数res+=(left-a[i].r+1)/2;left=a[i].r-1;right=a[i].r;}else { //两区间距离为偶数res+=(left-a[i].r+1)/2;left=a[i].r;right=a[i].r;}}else { //下一区间再当前区间右端if((a[i].l-right)&1) { //两区间距离为奇数res+=(a[i].l-right+1)/2;left=a[i].l;right=a[i].l+1;}else { //两区间距离为偶数res+=(a[i].l-right+1)/2;left=a[i].l;right=a[i].l;}}}}printf("%d\n",res);}return 0; }

 

总结

以上是生活随笔为你收集整理的Game（HDU-6669）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。