P5120题解

· · 题解

题解

USACO 2018.12月赛 银组 第二题

其实就是道膜你题只会做膜你题的蒟蒻

注意到因为有资历程度不同导致的的吃草顺序不同，这里最方便的方法就是用优先队列priority_queue，当然要配合着结构体，这时候就要自定义友元结构内比较运算符了（详情见代码）。

然后只要输出了然后按照到达时间拍一下序，用一个变量et表示当前吃草的奶牛的结束时间，然后从第一头遍历到最后一头膜你即可（详情见代码注释）。

注意点：

  1. 若没有等待的奶牛即直接让当前奶牛上去，不要push()再pop()了

  2. 记得特判当结束时间还小于当前奶牛的到达时间时要i--再来一次

  3. 遍历完最后记得将所有等待的奶牛一个个放进去吃草统计最大等待时间

代码

#include<stdio.h>
#include<algorithm>
#include<queue>
using namespace std;
int n,et,temp,res;
struct _cow
{
    int a,t,old; //a表示到达时间，t表示吃草时间，old表示资历
    friend bool operator < (_cow x,_cow y) //自定义比较运算符
    {
        return x.old>y.old;
    }
}cow[100010];
bool cmp(_cow x,_cow y)
{
    return x.a<y.a; //按到达时间从先到后排列（先来后到）
}
priority_queue<_cow> wait;
int main()
{
    scanf("%d",&n);
    for(register int i=0;i<n;++i)
    {
        scanf("%d%d",&cow[i].a,&cow[i].t);
        cow[i].old=i; //按输入的先后记录资历
    }
    sort(cow,cow+n,cmp); //排序
    et=cow[0].a+cow[0].t; //记录第一头奶牛的吃草结束时间
    for(register int i=1;i<n;++i)
    {
        if(cow[i].a>=et) //如果这头奶牛可以进去吃了
        {
            if(wait.empty()) et=cow[i].a+cow[i].t; //注意点1
            else
            {
                temp=et-wait.top().a; //用它的结束时间（即这头奶牛的开始吃草时间）减去它的到达时间来计算等待时间
                if(temp>res) res=temp; //找出最大值
                et+=wait.top().t; //更新结束时间
                wait.pop();
                if(et<cow[i].a) --i; //注意点2
                else wait.push(cow[i]); //否则再等
            }
        }
        else wait.push(cow[i]);
    }
    while(!wait.empty()) //注意点3
    {
        temp=et-wait.top().a;
        if(temp>res) res=temp;
        et+=wait.top().t;
        wait.pop();
    }
    printf("%d\n",res);
    return 0;
}