https://www.luogu.org/problemnew/show/P5120

题意：按资历顺序给出n头牛的到达时间和吃草持续时间，当有若干个牛都处于等待状态时，资历最大的优先吃草。

思路：暴力O(n^2)不行，考虑nlogn数据结构，用堆（优先队列）。将所有的牛按照到达时间排序排序，优先队列的优先级定义为资历顺序，排序后的牛入堆应该是顺序的，维护当前时间和当前牛指针，类似于单调队列那样，一头牛吃完草后，更新当前时间，把处于等待状态的牛入堆，每次堆顶就是要吃草的牛。

#include<bits/stdc++.h>
using namespace std;
#define maxn 100000+1000

int n,a[maxn],t[maxn],cur,ans,now;
int r[maxn];

struct HeapNode{
	int idx;
	bool operator < (HeapNode x)const{
		return idx>x.idx;
	}
};
priority_queue<HeapNode> Q;

bool cmp(int i,int j)
{
	return a[i]<a[j];
}

int main()
{
//	freopen("input.in","r",stdin);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d%d",&a[i],&t[i]),r[i]=i;
	sort(r+1,r+1+n,cmp);
	for(int i=1;i<=n;i++)if(a[r[i]]==a[r[1]])Q.push((HeapNode){r[i]}),cur++;
	now=a[r[1]];
	while(!Q.empty())
	{
		HeapNode u=Q.top();Q.pop();
		ans=max(ans,now-a[u.idx]);
		now+=t[u.idx];
		while(cur+1<=n&&a[r[cur+1]]<=now)
			Q.push((HeapNode){r[cur+1]}),cur++;
		
		if(cur+1<=n&&Q.empty())
		{
			now=a[r[cur+1]];
			int pos=cur+1;
			while(a[r[pos]]==a[r[cur+1]])
			{
				Q.push((HeapNode){r[cur+1]});
				cur++;
			}
		}
	}
	cout<<ans<<endl;
	return 0;	
}