求助
查看原帖
求助
596903
JoestarJX的小丑楼主2022/12/30 09:44

为啥这样写是过不了的

#include<bits/stdc++.h>
#define ld long double 
#define ll long long
using namespace std;
const int N=1e6+5;
int read(){
	int x=0;char ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x;
}
struct node{
	int x,p,c;
}a[N];
int n;
ll s1[N],s2[N],dp[N],q[N],head=1,tail=1;
ld X(int x){return s1[x];}
ld Y(int x){return dp[x]+s2[x];}
ld slope(int x,int y){return (Y(x)-Y(y))/(X(x)-X(y)+(X(x)==X(y)?1e-9:0));}
ll calc(int x,int y){return dp[x]+a[y].c+a[y].x*(s1[y]-s1[x])-(s2[y]-s2[x]);}
int main(){
	n=read();
	for(int i=1;i<=n;i++) a[i].x=read(),a[i].p=read(),a[i].c=read();
//	while(a[n].p==0&&n>=1) n--;
//	if(n==0){cout<<0;return 0;}
	for(int i=1;i<=n;i++) s1[i]=s1[i-1]+a[i].p;
	for(int i=1;i<=n;i++) s2[i]=s2[i-1]+a[i].x*a[i].p;
	for(int i=1;i<=n;i++){
		while(head<tail&&slope(q[head],q[head+1])<=a[i].x) head++;
		dp[i]=calc(q[head],i);
		while(head<tail&&slope(q[tail],q[tail-1])>=slope(i,q[tail])) tail--;
		q[++tail]=i;
//		cout<<dp[i]<<endl;
	}  
	int md=n;
	while(md>=1&&a[md].p==0) md--;
	if(md==0) cout<<0;
	else {
		ll ans=1e18;
		for(int i=md;i<=n;i++) ans=min(ans,dp[i]);
		cout<<ans;
	}
	return 0;
}

而改成这样就行……

#include<bits/stdc++.h>
#define ld long double 
#define ll long long
using namespace std;
const int N=1e6+5;
int read(){
	int x=0;char ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x;
}
struct node{
	int x,p,c;
}a[N];
int n;
ll s1[N],s2[N],dp[N],q[N],head=1,tail=1;
ld X(int x){return s1[x];}
ld Y(int x){return dp[x]+s2[x];}
ld slope(int x,int y){return (X(x)==X(y)?1e18:(Y(x)-Y(y))/(X(x)-X(y)));}
ll calc(int x,int y){return dp[x]+a[y].c+a[y].x*(s1[y]-s1[x])-(s2[y]-s2[x]);}
int main(){
	n=read();
	for(int i=1;i<=n;i++) a[i].x=read(),a[i].p=read(),a[i].c=read();
//	while(a[n].p==0&&n>=1) n--;
//	if(n==0){cout<<0;return 0;}
	for(int i=1;i<=n;i++) s1[i]=s1[i-1]+a[i].p;
	for(int i=1;i<=n;i++) s2[i]=s2[i-1]+a[i].x*a[i].p;
	for(int i=1;i<=n;i++){
		while(head<tail&&slope(q[head],q[head+1])<=a[i].x) head++;
		dp[i]=calc(q[head],i);
		while(head<tail&&slope(q[tail],q[tail-1])>=slope(i,q[tail])) tail--;
		q[++tail]=i;
//		cout<<dp[i]<<endl;
	}  
	int md=n;
	while(md>=1&&a[md].p==0) md--;
	if(md==0) cout<<0;
	else {
		ll ans=1e18;
		for(int i=md;i<=n;i++) ans=min(ans,dp[i]);
		cout<<ans;
	}
	return 0;
}
2022/12/30 09:44
加载中...