題干：

雖然制定了減肥食譜，但是湫湫顯然克制不住吃貨的本能，根本沒有按照食譜行動！?
于是，結果顯而易見…?
　　但是沒有什么能難倒高智商美女湫湫的，她決定另尋對策——吃沒關系，咱吃進去再運動運動消耗掉不就好了？?
　　湫湫在內心咆哮：“我真是天才啊~\(≧▽≦)/~”?

　　可是，大家要知道，過年回家多忙啊——幫忙家里做大掃除，看電影，看小說，高中同學聚餐，初中同學聚餐，小學同學聚餐，吃東西，睡覺，吃東西，睡覺，吃東西，睡覺……所以鍛煉得抽著時間來。?

　　但是，湫湫實在太忙了，所以沒時間去算一天有多少時間可以用于鍛煉，現在她把每日行程告訴你，拜托你幫忙算算吧~?

　　皮埃斯：一天是24小時，每小時60分鐘 Input輸入數據包括多組測試用例。?
每組測試數據首先是一個整數n，表示當天有n件事要做。?
接下來n行，第i行是第i件事的開始時間和結束時間，時間格式為HH:MM。?

[Technical Specification]?
1. 1 <= n <= 500000?
2. 00 <= HH <= 23?
3. 00 <= MM <= 59?
Output請輸出一個整數，即湫湫當天可以用于鍛煉的時間（單位分鐘）Sample Input 1 15:36 18:40 4 01:35 10:36 04:54 22:36 10:18 18:40 11:47 17:53Sample Output 1256 179

解題報告：

? ? 水題，包含一個合并區間的小模板，或者用開一個數組標記每個分鐘是否有安排。后者比較好想但是用時稍長。

ac代碼：（合并區間）

#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> using namespace std;struct Node {int s,e;} node[500000 + 5],nn[500000 + 5]; bool cmp(Node a,Node b) {return a.s<b.s;} int main() {int n;int cnt,maxx,minn;//int hour,minutes;int sum;while(~scanf("%d",&n) ) {sum=0;cnt=0;maxx=0;for(int i = 0 ; i<n; i++) {scanf("%d:%d",&hour,&minutes);node[i].s=hour*60+minutes;scanf("%d:%d",&hour,&minutes);node[i].e=hour*60+minutes;}sort(node,node+n,cmp);maxx=node[0].e;nn[cnt].s=node[0].s;nn[cnt].e=maxx;for(int i = 0; i<n; i++) {if(node[i].s > maxx) {nn[cnt++].e=maxx;//把maxx放入，并cnt++ nn[cnt].s=node[i].s;//把當前的start放入 maxx=node[i].e;nn[cnt].e=maxx;//為了防止i=n-1的情況（即讀到最后一個node了），因為此時可能maxx可能還未更新到nn.e中 }if(node[i].e>maxx) {maxx=node[i].e;nn[cnt].e=maxx;}}for(int i = 0; i<=cnt; i++) {sum+=nn[i].e-nn[i].s;}printf("%d\n",24*60-sum);}return 0 ;}

ac代碼2：（標記法）

#include<cstdio> #include<cstring> #include<iostream> using namespace std; int main() {int t;while(~scanf("%d",&t)) {int ans[2000];memset(ans, 0, sizeof(ans));for(int i = 0; i < t; i++) {int a, b, a1, b1;scanf("%d:%d", &a, &b);scanf("%d:%d", &a1, &b1);for(int j = a * 60 + b; j < a1 * 60 + b1; j++)ans[j] = 1;}int cnt= 0;for(int i = 0; i < 1440; i++) {if(!ans[i])cnt++;}printf("%d\n",cnt);}return 0;}

更：

ac代碼3：（好像還可以用線段樹？貼的代碼）

#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <cstdlib> #include <algorithm> #include <queue> #include <stack> #include <map> #include <set> #include <vector> #include <string> #define INF 1000000 #define eps 1e-8 #define MAXN (2000+10) #define MAXM (100000+10) #define Ri(a) scanf("%d", &a) #define Rl(a) scanf("%lld", &a) #define Rf(a) scanf("%lf", &a) #define Rs(a) scanf("%s", a) #define Pi(a) printf("%d\n", (a)) #define Pf(a) printf("%.2lf\n", (a)) #define Pl(a) printf("%lld\n", (a)) #define Ps(a) printf("%s\n", (a)) #define W(a) while((a)--) #define CLR(a, b) memset(a, (b), sizeof(a)) #define MOD 1000000007 #define LL long long #define lson o<<1, l, mid #define rson o<<1|1, mid+1, r #define ll o<<1 #define rr o<<1|1 #define PI acos(-1.0) #pragma comment(linker, "/STACK:102400000,102400000") #define fi first #define se second using namespace std; typedef pair<int, int> pii; struct Tree{int l, r, sum, lazy; }; Tree tree[MAXN<<2]; void PushUp(int o){tree[o].sum = tree[ll].sum + tree[rr].sum; } void PushDown(int o) {if(tree[o].lazy != -1){tree[ll].lazy = tree[rr].lazy = tree[o].lazy;tree[ll].sum = 0;tree[rr].sum = 0;tree[o].lazy = -1;} } void Build(int o, int l, int r) {tree[o].l = l; tree[o].r = r;tree[o].sum = r - l + 1; tree[o].lazy = -1;if(l == r) return ;int mid = (l + r) >> 1;Build(lson); Build(rson); } void Update(int o, int L, int R) {if(tree[o].l == L && tree[o].r == R){tree[o].lazy = 0;tree[o].sum = 0;return ;}PushDown(o);int mid = (tree[o].l + tree[o].r) >> 1;if(R <= mid) Update(ll, L, R);else if(L > mid) Update(rr, L, R);else {Update(ll, L, mid); Update(rr, mid+1, R);}PushUp(o); } int main() {int n;while(Ri(n) != EOF){Build(1, 0, 1440-1);for(int i = 0; i < n; i++){int sh, sm, th, tm;scanf("%d:%d%d:%d", &sh, &sm, &th, &tm);int s = sh * 60 + sm;int t = th * 60 + tm - 1;if(s <= t) Update(1, s, t);}Pi(tree[1].sum);}return 0; }

再附一個合并區間的錯誤代碼：（感謝cxsys大佬發現的這個問題點，幫助更好的理解區間合并與貪心問題。）

他寫的：

#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<cmath> #include<stdlib.h> using namespace std;struct node{int start_hour,start_mint,end_hour,end_mint; }; bool cmp(node a,node b) {if(a.start_hour==b.start_hour)return a.start_mint<b.start_mint;return a.start_hour<b.start_hour; } struct node t[500005]; int main() {int n;while(scanf("%d",&n)!=EOF){memset(t,0,sizeof(t));int sum=0;for(int i=0;i<n;i++){scanf("%d:%d%d:%d",&t[i].start_hour,&t[i].start_mint,&t[i].end_hour,&t[i].end_mint);}sort(t,t+n,cmp);for(int i=0;i<n;i++){if(sum==0)sum=(t[i].end_hour-t[i].start_hour)*60+(t[i].end_mint-t[i].start_mint);if(t[i+1].start_hour*60+t[i+1].start_mint>t[i].end_hour*60+t[i].end_mint)sum=sum+(t[i+1].end_hour-t[i+1].start_hour)*60+(t[i+1].end_mint-t[i+1].start_mint);if(t[i+1].end_hour*60+t[i+1].end_mint>t[i].end_hour*60+t[i].end_mint)sum=sum+(t[i+1].end_hour-t[i].end_hour)*60+(t[i+1].end_mint-t[i].end_mint);if(t[i+1].end_hour*60+t[i+1].end_mint<t[i].end_hour*60+t[i].end_mint)continue;} printf("%d\n",1440-sum);}return 0; }

有點丑陋，不易閱讀，我給他修改了下以后的代碼：

#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<cmath> #include<stdlib.h> using namespace std;struct node{int start_hour,start_mint,end_hour,end_mint;int s,e; }; bool cmp(node a,node b) {if(a.start_hour==b.start_hour)return a.start_mint<b.start_mint;return a.start_hour<b.start_hour; } struct node t[500005]; int main() {int n;while(scanf("%d",&n)!=EOF){memset(t,0,sizeof(t));int sum=0;for(int i=0;i<n;i++){scanf("%d:%d%d:%d",&t[i].start_hour,&t[i].start_mint,&t[i].end_hour,&t[i].end_mint);t[i].s=t[i].start_hour*60+t[i].start_mint;t[i].e=t[i].end_hour*60+t[i].end_mint;}sort(t,t+n,cmp);for(int i=0;i<n;i++){if(sum==0)sum=t[i].e-t[i].s;if(t[i+1].s>=t[i].e)sum=sum+t[i+1].e-t[i+1].s;if(t[i+1].e>=t[i].e)sum=sum+(t[i+1].e-t[i].e;if(t[i+1].e<t[i].e)continue;} printf("%d\n",1440-sum);}return 0; }

比如一個例子：

這么算應該是4+0+0.5小時，但其實是4小時

總結：合并區間的模板可否在優化一下？

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的【HDU - 4509】湫湫系列故事——减肥记II（合并区间模板 or 离散化标记 or 线段树）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。