Home » 国际竞赛 » Details

USACO 2018 December Contest Silver 2 Convention II

Category: 国际竞赛, 计算机国际竞赛 Date: 2018年12月20日下午12:25

Despite long delays in airport pickups, Farmer John's convention for cows interested in eating grass has been going well so far. It has attracted cows from all over the world.

The main event of the conference, however, is looking like it might cause Farmer John some further scheduling woes. A very small pasture on his farm features a rare form of grass that is supposed to be the tastiest in the world, according to discerning cows. As a result, all of the cows at the conference ( ) want to sample this grass. This will likely cause long lines to form, since the pasture is so small it can only accommodate one cow at a time.

Farmer John knows the time that each cow plans to arrive at the special pasture, as well as the amount of time she plans to spend sampling the special grass, once it becomes her turn. Once cow starts eating the grass, she spends her full time of before leaving, during which other arriving cows need to wait. If multiple cows are waiting when the pasture becomes available again, the cow with the highest seniority is the next to be allowed to sample the grass. For this purpose, a cow who arrives right as another cow is finishing is considered "waiting". Similarly, if a number of cows all arrive at exactly the same time while no cow is currently eating, then the one with highest seniority is the next to eat.

Please help FJ compute the maximum amount of time any cow might possibly have to wait in line (between time and the time the cow begins eating).

INPUT FORMAT (file convention2.in):

The first line of input contains . Each of the next lines specify the details of the cows in order of seniority (the most senior cow being first). Each line contains and for one cow. The 's are positive integers each at most , and the 's are positive integers at most .

OUTPUT FORMAT (file convention2.out):

Please print the longest potential waiting time over all the cows.

SAMPLE INPUT:

SAMPLE OUTPUT:

In this example, we have 5 cows (numbered 1..5 according to their order in the input). Cow 4 is the first to arrive (at time 10), and before she can finish eating (at time 27) cows 1 and 3 both arrive. Since cow 1 has higher seniority, she gets to eat next, having waited 2 units of time beyond her arrival time. She finishes at time 30, and then cow 3 starts eating, having waited for 10 units of time beyond her starting time. After a gap where no cow eats, cow 5 arrives and then while she is eating cow 2 arrives, eating 5 units of time later. The cow who is delayed the most relative to her arrival time is cow 3.

Problem credits: Brian Dean

USACO 2018 December Contest Silver 2 Convention II题解(翰林国际教育提供，仅供参考)

优先队列（或set）贪心
第一次排序，按到达时间排。
然后一个while
如果有牛的到达时间小于等于当前时间，就加入进来。
特别的注意到加入到堆里之后，牛是按标号排的。
如果加了之后，集合还是空的，那么说明这段时间一个牛都没有，将时间设为下一头牛到达的时间即可，并且continue直接执行下一轮循环。
然后思考下一头开始的牛是谁，他应该是当前集合中标号最小的。
更新一下答案。
更新一下当前时间
把这头牛删掉，进入下一轮。

#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
int n;
pair<pair<int, int>, int> a[100020];
int main() {
    freopen("convention2.in", "r", stdin);
    freopen("convention2.out", "w", stdout);
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &a[i].X.X, &a[i].Y);
        a[i].X.Y = i;
    }
    sort(a, a + n);
    int z = 0, i = 0, t = 0;
    set<pair<pair<int, int>, int> > s;
    while (true) {
        while (i < n && a[i].X.X <= t) {
            swap(a[i].X.X, a[i].X.Y);
            s.insert(a[i++]);
        }
        if (s.size() == 0) {
            if (i == n) {
                break;
            }
            t = a[i].X.X;
            continue;
        }
        z = max(z, t - s.begin()->X.Y);
        t += s.begin() -> Y;
        s.erase(s.begin());
    }
    printf("%dn", z);
    return 0;
}