感雨時刻の整理

一、題目描述

給定一個變量 m, 之后是 m 組時間段
以“時分-時分”給出
如樣例1輸入：

4
1148-1210
1323-1401
1106-1123
1129-1203

要求將其轉(zhuǎn)化之后再合并
轉(zhuǎn)化方式為，起始時間向前移動到能被5整除，結(jié)束時間向后移動到能被5整除，如：
1148-1210
轉(zhuǎn)化為
1145-1210
合并方式為，將重復的時間段合并
如樣例1輸出：

1105-1210
1320-1405

二、算法分析及代碼

1. 時間的轉(zhuǎn)化與輸出

（1）轉(zhuǎn)化

int change(int x,int v){
   
    int res=1;
    int a=x/100;
    int b=x%100;
    res+=a*12;
    res+=b/5;
    if(v==2 && b%5!=0) res++;
    return res;
}

x 代表需要轉(zhuǎn)化的時間，v=1 代表其是起始時間，v=2 代表其是結(jié)束時間。
① 對于起始時間
轉(zhuǎn)化方式為以5分鐘為一段來整除
比如 0001/5=0,
則 0001轉(zhuǎn)化為0
② 對于結(jié)束時間
轉(zhuǎn)化方式為以5分鐘為一段來整除，再加1
比如 0006/5=1,
則 0006轉(zhuǎn)化為1+1=2
特別的是，當結(jié)束時間本身就能被5整除時，則不用加1
比如 0010/5=2, 且0010 mod 5=0,
則0010轉(zhuǎn)化為2

為了防止數(shù)組下標越界，筆者將轉(zhuǎn)化后的時間又向后移了一位，所以 res 初始時為1

（2）輸出

void print(int l,int r){
   
    l--;
    r--;
    int a=l/12;
    int b=5*(l%12);
    int c=r/12;
    int d=5*(r%12);
    printf("%0*d",2,a);
    printf("%0*d",2,b);
    printf("-");
    printf("%0*d",2,c);
    printf("%0*d",2,d);
    printf("\n");
}

l 和 r 都是轉(zhuǎn)化處理后的時間，先將其后移的一位移回去，再還原時和分，然后用 printf 語句的占位方式將其輸出

printf("%0*d",2,a);

表示將該整數(shù)前面用0填充，填充之后的位數(shù)為2

print(1,2)

輸出為：

0000-0005

2. 解法1-利用差分進行區(qū)間維護（時間復雜度O(n)）

（1）一個思路
將時間全部按上述 change 函數(shù)轉(zhuǎn)化后，獲得了若干個時間段，這些時間段轉(zhuǎn)化后的值不會超過24*12+1=2，可以開一個長度大于2的數(shù)組 p, 對于每個時間段[l,r], 將 l 到 r 之間的值全部加1，最后統(tǒng)計所有連續(xù)的非0序列&