BZOJ 5142 [Usaco2017 Dec]Haybale Feast

题目大意

给你N个东西，每个东西都有两个属性X，Y。请你求出一个连续的区间使得区间内的东西的属性X的和≥M,且属性Y的最大值最小。

这题可真有趣……

我的想法是将所有东西按照Y的大小从大到小排序，之后从大到小往里加，同时维护连续的空区间X值和。如果已经没有区间X值和≥m的话那就输出最后加进去的那个东西的Y值即可。

实际上双指针就可以求出所有满足条件的区间……我沙茶了= =

#include <set>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 100010
struct point{int v,id;}po[N];
bool cmp(const point &X,const point &Y){return X.v<Y.v;}
int n;
long long m,f[N];
multiset<int>p;
multiset<long long>d;
int main()
{
	scanf("%d%lld",&n,&m);
	for(int i=1;i<=n;++i) scanf("%lld%d",f+i,&po[i].v),f[i]+=f[i-1],po[i].id=i;
	f[n+1]=f[n];
	sort(po+1,po+n+1,cmp);
	p.insert(0),p.insert(n+1),d.insert(f[n]);
	while(*d.rbegin()>=m)
	{
		int a,b;
		set<int>::iterator it=p.upper_bound(po[n].id);b=*it,a=*--it;
		p.insert(po[n].id);
		d.erase(d.find(f[b]-f[a]));
		d.insert(f[po[n].id]-f[a]);
		d.insert(f[b]-f[po[n].id]);
		n--;
	}
	printf("%d\n",po[n+1].v);
}