1 条题解

  • 0
    @ 2026-2-4 23:06:01
    #include <bits/stdc++.h>
    const int N=2e5+10;
    using namespace std;
    typedef long long ll;
    bool debug1;
    int n,l=1,r;
    int q[N];
    ll sum,ans,f[N],w[N],dd[N],d[N],s[N];
    bool debug2;
    double slope(int i,int j){
    	return 1.0*(s[i]*d[i]-s[j]*d[j])/(s[i]==s[j]?1e-9:s[i]-s[j]);
    }
    int main(){
    //	freopen("data.in","r",stdin);
    //	freopen("my.out","w",stdout);
    //	cout<<((&debug2-&debug1)/1024.0/1024.0)<<endl;
    	scanf("%d",&n);
    	for(int i=1;i<=n;i++){
    		scanf("%lld%lld",&w[i],&dd[i]);
    		s[i]=s[i-1]+w[i];
    	}
    	for(int i=n;i>=1;i--)
    		d[i]=d[i+1]+dd[i];
    	for(int i=1;i<=n;i++)
    		sum+=d[i]*w[i];
    	for(int i=1;i<=n;i++){
    		while(l<r&&slope(i-1,q[r])>=slope(q[r],q[r-1]))
    			r--;
    		q[++r]=i-1;
    		while(l<r&&slope(q[l+1],q[l])>=d[i])
    			l++;
    		int j=q[l];
    		f[i]=sum-(s[j]*d[j]-s[j]*d[i]+s[i]*d[i]);
    	}
    	ans=f[1];
    	for(int i=1;i<=n;i++)
    		ans=min(ans,f[i]);
    	printf("%lld",ans);
    	return 0;
    }
    
    • 1

    *【斜率优化】[CEOI 2004] 锯木厂选址

    信息

    ID
    1801
    时间
    200ms
    内存
    512MiB
    难度
    6
    标签
    递交数
    38
    已通过
    13
    上传者