新的问题
查看原帖
新的问题
1332453
__Florie_楼主2024/8/11 11:30

我的60pts和其他人的原因貌似不一样...

找不出来什么问题,求教!

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ldb long double

int n,s,t,f,tq[300010],fq[300010],dp[300010];
int l,r,qu[300010];
//dp[j]=(s+tq[i])*fq[j]+dp[i]-tq[i]*fq[i]-s*fq[n];
bool check(int mid,int k){// mid是队列中点的下标(偏左) 
	int a=dp[qu[mid+1]]-dp[qu[mid]];
	int b=fq[qu[mid+1]]-fq[qu[mid]];
	if(a>b*k) return 1;
	else return 0;
}
int point(int l,int r,int k){
	int lhs=l,rhs=r,mid;
	if(lhs==rhs) return qu[lhs];
	while(lhs<rhs){
		mid=(lhs+rhs)>>1;
		if(check(mid,k)==1) rhs=mid;
		else lhs=mid+1;
	}
	return qu[lhs];
}

signed main(){
	cin>>n>>s;
	for(int i=1;i<=n;i++){
		scanf("%d%d",&t,&f);
		tq[i]=tq[i-1]+t;
		fq[i]=fq[i-1]+f;
	}
	l=r=1; qu[1]=0;// l==r表示队列中有一个元素 
	for(int i=1;i<=n;i++){
		int k=s+tq[i],p;// 斜率 
		p=point(l,r,k);// 在队列中查找斜率首个大于k的下标 
		dp[i]=dp[p]-(s+tq[i])*fq[p]+tq[i]*fq[i]+s*fq[n];
		while(l<r){
			int a=dp[i]-dp[qu[r]]; int c=dp[qu[r]]-dp[qu[r-1]];
			int b=fq[i]-fq[qu[r]]; int d=fq[qu[r]]-fq[qu[r-1]];
			if(a*d<=b*c) r--;
			else break;
		}
		qu[++r]=i;
	}
	printf("%lld",dp[n]);
	return 0;
}
2024/8/11 11:30
加载中...