不知道自己写的什么滚木代码。

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define se second
const int N=1e5+10;
struct nd{int st,ti,zl;}cow[N];
bool cmp(nd n1,nd n2)
{
	return n1.st<n2.st;
}
priority_queue<pii,vector<pii>,greater<pii> >q;
int ed[N];
int main()
{
	int n;scanf("%d",&n);
	for(int i=1,a,t;i<=n;i++)
	{
		scanf("%d%d",&a,&t);
		cow[i]={a,t,i};
	}
	sort(cow+1,cow+n+1,cmp);
	int id=1;q.push({cow[1].zl,1});
	while(id<n&&cow[id+1].st==cow[id].st)id++,q.push({cow[id].zl,id});
	int x=q.top().se;q.pop();ed[x]=cow[x].st;
	for(int t=cow[x].st;;)
	{
		while(id<n&&cow[id+1].st<=t+cow[x].ti)id++,q.push({cow[id].zl,id});
		if(id==n&&q.empty())break;
		t+=cow[x].ti;
		if(!q.empty())x=q.top().se,q.pop();
		else x=++id,t=cow[x].st;
		ed[x]=t;
	}
	int ans=0;
	for(int i=1;i<=n;i++)ans=max(ans,ed[i]-cow[i].st);
	printf("%d\n",ans);
	return 0;
}

一道模拟题

思路

大致就是分类讨论。根据到达时间的先后顺序考虑一头奶牛 $w$ 到达后的情况

1. 草地上没有奶牛在吃草。

   <1> 已经有奶牛在排队。

   让队首的奶牛去吃草，如果队首奶牛吃完草的时间仍然比 $w$ 的到达时间早，则重新讨论 $w$ 到达时的情况，否则让 $w$ 去排队。

   <2> 没有奶牛在排队。

   $w$ 可直接去吃草，不需要等待。

2. 草地上已经有奶牛在吃草。

   $w$ 要去排队。

解释一下 1.<1>的情况下为什么要这么做。

因为我们只有在一头奶牛到达时才去看草地上有没有奶牛并进行出队操作，中间会间隔很长一段时间，出队操作相当于延迟了。

比如： 奶牛 2到达时奶牛 1在吃草，那么奶牛 2入队等待，直到 奶牛 3 到达时状态才会改变。假设奶牛 3 到达时间为 $10$，而奶牛 2在 $3$ 时就可以进去吃草，并在 $5$ 时吃完离开。奶牛3 在 $10$时 到达时状态仍是 奶牛1 在吃草，奶牛2在排队，但奶牛 2 实际上是吃完离开的，所以我们要像上面所说的去操作。

如何判断有没有奶牛在草地上

在每个奶牛进入草地吃草时记录它吃完草离开的时间，若后来的奶牛到达时间 大于 这个时间，说明它已经离开了，草地上没有奶牛。反之则有。

如何排队

题目说要根据资历来排队，我们就使用 STL 中的优先队列priority_queue，相当于大根堆。并将元素取反放入，让其实现小根堆的功能。

答案的更新

在每个奶牛去吃草的时候计算一下它等待了多久，并更新答案。

注意在遍历完所有奶牛之后队伍中可能还有奶牛在排队，要将它们全部出队，并更新答案。

Before the Code

因为思路和第二篇题解一样，代码就差不多，不想放来着……但是本题解主要是讲解思路，代码可以辅助理解并展示实现细节，就放上了。如果发现本题解中的错误或有疑问，欢迎评论或私信。

Enjoy the Code

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn=100005;
int n,vis,ans;
struct node{
	int a,t,id,ed;
	bool operator <(const node x)const
	{
	if(x.a<a)
	return 0;
	if(x.a>a)
	return 1;
	return x.id>id;
	}
}c[maxn];
priority_queue<pair<int,int> >q;

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&c[i].a,&c[i].t);
		c[i].id=i;
	}
	sort(c+1,c+1+n);
	int x;
	vis=c[1].a+c[1].t;
	for(int i=2;i<=n;i++)
	{
		if(c[i].a>=vis)// the last cow has done
		{
			if(!q.empty())//need wait
			{
				int x=q.top().second;
				q.pop();
				ans=max(ans,vis-c[x].a);
				vis+=c[x].t;
				if(vis<c[i].a)
				--i;
				else			
				q.push(make_pair(-c[i].id,i));
			}else// no need to wait
				vis=c[i].a+c[i].t;
		}
		else// the last cow hasn't done
		{
			q.push(make_pair(-c[i].id,i));
		}
	}
	while(!q.empty())
	{
		int x=q.top().second;
		q.pop();
		ans=max(vis-c[x].a,ans);
		vis+=c[x].t;
	}
	printf("%d",ans);
	return 0;
}

See Ya ！