为啥这样写是过不了的
#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;
}