首页 > 代码库 > HDU 4883 TIANKENG’s restaurant(区间选点)
HDU 4883 TIANKENG’s restaurant(区间选点)
HDU 4883 TIANKENG’s restaurant
题目链接
题意:给定一些时间作为区间,和一个人数,问要安排多少人去看管(一个人只能看管一个人)
思路:普通的区间选点问题,一个区间拆成一个进入点一个出去点,然后排序循环求答案即可
代码:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N = 20005; struct Man { int v, t; Man() {} Man(int v, int t) {this->v = v; this->t = t;} } m[N]; bool cmp(Man a, Man b) { if (a.t != b.t) return a.t < b.t; return a.v < b.v; } int n, t, mn; int main() { scanf("%d", &t); while (t--) { mn = 0; scanf("%d", &n); for (int i = 0; i < n; i++) { int a, b, c, d, e; scanf("%d%d:%d%d:%d", &a, &b, &c, &d, &e); int t1 = b * 60 + c; int t2 = d * 60 + e; m[mn++] = Man(a, t1); m[mn++] = Man(-a, t2); } sort(m, m + mn, cmp); int ans = 0, sum = 0; for (int i = 0; i < mn; i++) { sum += m[i].v; ans = max(ans, sum); } printf("%d\n", ans); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。