求助 调不出来了
查看原帖
求助 调不出来了
406955
itianqi楼主2022/6/13 11:49

好像是二分部分错了,但一直调不出来。

#include<bits/stdc++.h>
#define MAXN 300005
#define LL long long
using namespace std;
LL n,s;
LL t[MAXN],f[MAXN];
LL sf[MAXN],st[MAXN];
LL dp[MAXN];
LL q[MAXN];
int h=1,l=1;
LL up(int j,int k){
	return (f[j]-f[k]);
}
LL down(int j,int k){
	return (sf[j]-sf[k]);
}
int main()
{
	cin>>n>>s;
	for(int i=1;i<=n;i++){
		scanf("%lld%lld",&t[i],&f[i]);
		st[i]=st[i-1]+t[i];
		sf[i]=sf[i-1]+f[i];
	}
	
	for(int i=1;i<=n;i++){
		int j=q[h];
		int L=h+1,R=l;
		
		while(L<=R){
			int mid=(L+R)/2;
			if(up(q[mid],q[mid-1])<=(st[i]+s)*down(q[mid],q[mid-1]))
			{
				j=q[mid];
				L=mid+1;
			}
			else R=mid;
		}
		dp[i]=dp[j]+(st[i]*(sf[i]-sf[j])+s*(sf[n]-sf[j]));
  		while(h<l&&up(i,q[l])*down(q[l],q[l-1])<=up(q[l],q[l-1])*down(i,q[l])) l--;
			q[++l]=i;
	}
	cout<<dp[n];
 return 0;
}


2022/6/13 11:49
加载中...