双指针60分求助
查看原帖
双指针60分求助
379113
dtrthg楼主2023/8/23 12:27

思路:用线段树维护最小值,用双指针法找合法区间并与当前答案取min,但wa了4个点qwq

代码:

#include <bits/stdc++.h>
using namespace std;
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define of(i,a,b) for(int i=a;i>=b;--i)
#define ll long long
const int inf=0x3f3f3f3f;
const ll INF=9e18;
const int mod=-1;//lL?
const int Maxn=1e5+10;
ll f[Maxn],s[Maxn],tree[Maxn<<2];
int n,m;
void build(int L,int R,int p)
{
	if(L==R) {tree[p]=s[L]; return ;}
	ll mid=L+R>>1;
	build(L,mid,p<<1); build(mid+1,R,p<<1|1);
	tree[p]=std::max(tree[p<<1],tree[p<<1|1]);
}
ll query(int L,int R,int p,int t_l,int t_r)
{
	if(t_l<=L&&R<=t_r) return tree[p];
	ll mid=L+R>>1;
	ll ans=-INF;
	if(t_l<=mid) ans=std::max(ans,query(L,mid,p<<1,t_l,t_r));
	if(t_r>mid)  ans=std::max(ans,query(mid+1,R,p<<1|1,t_l,t_r));
	return ans;
}
int main()
{
	scanf("%d%d",&n,&m);
	fo(i,1,n) scanf("%lld%lld",&f[i],&s[i]);
	build(1,n,1);
	int pos1,pos2; pos1=pos2=1;
	ll cnt=0,ans=INF;
	while(pos2<=n)
	{
		while(pos2<=n&&cnt<m) cnt+=f[pos2++];
		if(cnt<m) break;
		if(cnt>=m) ans=std::min(ans,query(1,n,1,pos1,pos2));
		cnt-=f[pos1++];
	}
	printf("%lld\n",ans); 
	return 0;
}
/*
in1:

out1:

*/

2023/8/23 12:27
加载中...