2019|2019 年百度之星·程序设计大赛 - 初赛一Game HDU 6669 (实现，贪心) 2019年百度之星·程序设计大赛

Game
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 833 Accepted Submission(s): 200
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
样例描述
选取10为起点，经过的轨迹为10-12-14-16-18-20。
Source
2019 年百度之星·程序设计大赛 - 初赛一
思路：
由于题目要求一次完成n个任务，所以先把给定的n个区间，缩并为cnt个不相交的区间，那么就从第一个依次贪心的进入每一个区间，
【2019|2019 年百度之星·程序设计大赛 - 初赛一Game HDU 6669 (实现，贪心)】用第二个区间和第一个区间的位置关系，判断初始位置，
当从当前now移动到第i个区间需要移动的距离是奇数时，根据第i+1（如果存在的话）来判断是否需要多跳一个位置即可。

细节见代码：

#include #include #include #include #include #include #include #include #include #include #include #define ALL(x) (x).begin(), (x).end() #define sz(a) int(a.size()) #define all(a) a.begin(), a.end() #define rep(i,x,n) for(int i=x; i #define pll pair #define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) #define MS0(X) memset((X), 0, sizeof((X))) #define MSC0(X) memset((X), '\0', sizeof((X))) #define pb push_back #define mp make_pair #define fi first #define se second #define eps 1e-6 #define gg(x) getInt(&x) #define chu(x) cout<<"["<<#x<<" "<<(x)<<"]"<> t; while (t--) { cnt=0; cin >> n; repd(i, 1, n) { cin >> a[i].fi >> a[i].se; } b[++cnt]=a[1]; repd(i,2,n) { if(a[i].fi>b[cnt].se) { b[++cnt]=a[i]; }else if(a[i].seb[1].se) { now=b[1].se; }else { now=b[1].fi; } repd(i,2,cnt) { int dis; // 需要移动的距离 if(b[i].fi>now) { dis=b[i].fi-now; if(dis&1) { if(i+1<=cnt&&(b[i].se-b[i].fi)>1&&b[i+1].fi>b[i].fi) { now=b[i].fi+1; }else { now=b[i].fi; } }else { now=b[i].fi; } ans+=dis/2; if(dis&1) { ans++; } }else { dis=now-b[i].se; if(dis&1) { if(i+1<=cnt&&(b[i].se-b[i].fi)>1&&b[i+1].se= '0' && ch <= '9') { *p = *p * 10 + ch - '0'; } } }

转载于:https://www.cnblogs.com/qieqiemin/p/11374051.html