首页 > 代码库 > TIANKENG’s restaurant
TIANKENG’s restaurant
题目链接
- 题意:
n组人,每组一行输入:人数,到达时间,离开时间。问人数最多是多少(如果同一时刻有人到有人离开,那么先让人离开) - 分析:
把一组人拆成两个点,左端点和右端点,从左向右扫描。如果遇到一个左端点,加入集合中;如果遇到一个右端点,就把集合中对应的点删去即可。
const int MAXN = 110000; struct Node { int num, isr, id, time; bool operator< (const Node& rhs) const { if (time != rhs.time) return time < rhs.time; return isr > rhs.isr; } } ipt[MAXN]; int main() { int T, a, b, c, d, n, num; RI(T); FE(kase, 1, T) { RI(n); REP(i, n) { scanf("%d %d:%d %d:%d", &num, &a, &b, &c, &d); int x = i << 1, y = x | 1; ipt[x].isr = 0; ipt[x].time = a * 60 + b; ipt[y].isr = 1; ipt[y].time = c * 60 + d; ipt[x].id = ipt[y].id = i; ipt[x].num = ipt[y].num = num; } n <<= 1; sort(ipt, ipt + n); set<int> st; int ans = 0, tans = 0; REP(i, n) { if (ipt[i].isr) { st.erase(ipt[i].id); tans -= ipt[i].num; } else { st.insert(ipt[i].id); tans += ipt[i].num; } ans = max(ans, tans); } WI(ans); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。