HDU 4883 TIANKENG’s restaurant （區間更新）

HDU 4883 TIANKENG’s restaurant （區間更新）

Problem Description TIANKENG manages a restaurant after graduating from ZCMU, and tens of thousands of customers come to have meal because of its delicious dishes. Today n groups of customers come to enjoy their meal, and there are Xi persons in the ith group in sum. Assuming that each customer can own only one chair. Now we know the arriving time STi and departure time EDi of each group. Could you help TIANKENG calculate the minimum chairs he needs to prepare so that every customer can take a seat when arriving the restaurant?

Input The first line contains a positive integer T(T<=100), standing for T test cases in all.

Each cases has a positive integer n(1<=n<=10000), which means n groups of customer. Then following n lines, each line there is a positive integer Xi(1<=Xi<=100), referring to the sum of the number of the ith group people, and the arriving time STi and departure time Edi(the time format is hh:mm, 0<=hh<24, 0<=mm<60), Given that the arriving time must be earlier than the departure time.

Pay attention that when a group of people arrive at the restaurant as soon as a group of people leaves from the restaurant, then the arriving group can be arranged to take their seats if the seats are enough.

Output For each test case, output the minimum number of chair that TIANKENG needs to prepare.

Sample Input

2
2
6 08:00 09:00
5 08:59 09:59
2
6 08:00 09:00
5 09:00 10:00

Sample Output

11
6

這道題目很容易想到用線段樹更新，比賽的時候也確實用線段樹過了，但實際上用線段樹更新有些大材小用，因為題目只需查詢一次，並沒有動態更新和動態查詢。

可以用一個sum數組記錄該點總共的人數，輸入的時候可預處理第i批客人的變化情況。來的時候 sum[i]就加上相應的人數，走的時候sum[i]就減去相應的人數。

可以得到地推公式 sum[i] += sum[i-1]; i表示時間的推移，從第0分鐘一直可以推到結束時間。因為期間不用再次更新也無需查詢，這種算法要比線段樹更具優勢。

#include 
#include 
#include 
#include 
#include 
#define lson o<<1, l, m
#define rson o<<1|1, m+1, r
using namespace std;
typedef long long LL;
const int maxn = 1500;
const int MAX = 0x3f3f3f3f;
const int mod = 1000000007;
int t, n;
int sum[maxn];
int main()
{
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        memset(sum, 0, sizeof(sum));
        for(int i = 0; i < n; i++) {
            int tmp, h1, m1, h2, m2;
            scanf("%d %d:%d %d:%d", &tmp, &h1, &m1, &h2, &m2);
            int st = h1*60+m1;
            int en = h2*60+m2;
            sum[st] += tmp;
            sum[en] -= tmp;
        }
        int ans = sum[0];
        for(int i = 1; i <= 1440; i++) {
            sum[i] += sum[i-1];
            ans = max(ans, sum[i]);
        }
        printf("%d\n", ans);
    }
    return 0;
}