盒子
盒子
文章目录
  1. 题目
  2. 题意
  3. 思路
  4. 代码
  5. 更新日志

HDU 4883 TIANKENG's restaurant

题目

源地址:http://acm.hdu.edu.cn/showproblem.php?pid=4883

题意

有一家餐厅,有n组人,每组包括Xi个人,在某一个时间段来到餐厅。问餐厅最少需要多少张凳子可以让每一个时刻所有在餐厅的人都有位子。

思路

把到达的和离开的时间按照从小到大排序,遇到到达时加上来的人数,遇到离开时减去离开的人数,遍历求出最大值即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int N = 10000 + 10;
int n, t;
pair<int, int> a[N + N];
int main () {
scanf("%d", &t);
int c, x, xx, y, yy, cnt;
while(t--) {
scanf("%d", &n);
cnt = 0;
for (int i = 0; i < n; i++) {
scanf("%d%d:%d%d:%d", &c, &x, &xx, &y, &yy);
a[cnt++] = make_pair(x * 60 + xx, c);
a[cnt++] = make_pair(y * 60 + yy, -c);
}
sort(a, a + cnt);
int ans = 0, sum = 0;
for (int i = 0; i < cnt; i++) {
sum += a[i].second;
ans = max(ans, sum);
}
printf("%d\n", ans);
}
return 0;
}

更新日志

  • 14040955 2015-07-17 16:01:31 Accepted 4883 577MS 1748K 643 B G++ SIO__Five