洛谷P4085 [USACO17DEC]Haybale Feast G 题解

题目链接：P4085 [USACO17DEC]Haybale Feast G

题意：给定 $2$ 个由 $N$ 个数字组成的数列 $F,S$ ，需要找到使得 $\sum_{k=i}^{j}F_k\ge M$ 的 $i,j$ 并输出在所有满足条件的 $i,j$ 中，$\max(S_i,S_{i+1},…S_{j-1},S_{j}$)的最小值，数列里每个数非负

解法一

由非负这个条件我们可以得到一个重要结论

对于区间 $A,B$ ，若 $A \subsetneqq B$ ，则 $A$ 的最大值小于等于 $B$ 的最大值

因此具有单调性

那么我们可以二分答案解决此题

每次判断就 $O(n)$ 扫一遍看看有没有满足条件的区间即可

时间复杂度 $O(n\log \max \{S_i\})$

代码如下

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define R register
#define MAXN (int)(1e5+5)
int n,k,inf;
int a[MAXN],b[MAXN];
bool check(R int mx)
{
	R int res=0;
	for(R int i=1; i<=n; i++)
	{
		if(b[i]>mx)res=0; // 该区间不合法
		else res+=a[i]; // 否则加上
		if(res>=k)return 1; // 有答案
	}
	return 0;
}
void proc(R int l,R int r)
{
	while(l<=r)
	{
		R int mid=(l+r)>>1;
		if(check(mid))r=mid-1;
		else l=mid+1;
	}
	printf("%lld\n",l);
}
signed main()
{
	scanf("%lld%lld",&n,&k);
	for(R int i=1; i<=n; i++)
	{
		scanf("%lld%lld",&a[i],&b[i]);
		inf=max(inf,b[i]);
	}
	proc(0,inf);
	return 0;
}

解法二

显然第一维限制我们可以用尺取法搞定

因为我们要找到的 $i,j$ 一定是尽可能短的区间

那么第二维限制我们可以用单调队列搞定

为什么？因为尺取法的端点是单调不下降的

时间复杂度 $O(n)$

代码如下

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define R register
#define MAXN (int)(1e5+5)
#define INF 0x3f3f3f3f3f3f3f3f
template<typename T>inline void read(R T &k)
{
	R char ch=getchar(); R T x=0,f=1;
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	k=x*f;
}
int n,k,mn=INF;
int a[MAXN],b[MAXN];
deque<int> q; // 我懒 qwq
void push(R int idx)
{
	while(!q.empty()&&b[q.back()]<=b[idx])q.pop_back();
	q.push_back(idx);
}
void pop(R int idx)
{
	while(!q.empty()&&q.front()<=idx)q.pop_front();
}
void proc(R int l,R int r)
{
	R int now=0,mn=INF;
	while(1)
	{
		while(now<k&&r<n)
		{
			now+=a[++r];
			push(r); // 拓展右端点时往单调队列里塞下标
		}
		if(now>=k)mn=min(mn,b[q.front()]);
		else break;
		pop(l); // 收缩左端点时弹单调队列队头
		now-=a[l++];
	}
	printf("%lld\n",mn);
}
signed main()
{
	read(n);read(k);
	for(R int i=1; i<=n; i++)
		read(a[i]),read(b[i]);
	proc(1,0);
	return 0;
}