求助斜率优化叉积维护和斜率维护精度问题

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<ld,int> pdi;
#define x first 
#define y second
const int N=100010;
int n,k;
struct node {
    ld v;
    int k;
}f[N];
int q[N],hh=0,tt=-1;
inline ld val(int i,int j,ld d) {
    return f[j].v+d+1-1.0*i/j;
}
// inline pdi get(int i,int j) {
//     return {(1.0/i-1.0/j),f[i].v-f[j].v};
// }
// inline bool check(pdi a,pdi b) {
//     return a.x*b.y>a.y*b.x;
// }
inline ld slope(int i,int j) {
    return (f[i].v-f[j].v)/(1.0/i-1.0/j);
}
inline void calc(ld d) {
    hh=0,tt=-1;
    f[n]={0.0,0}; 
    q[++tt]=n;
    for(int i=n-1;i>=0;i--) {
        
        while(hh<tt&&val(i,q[hh+1],d)>val(i,q[hh],d)) hh++;
        f[i].v=val(i,q[hh],d),f[i].k=f[q[hh]].k+1;
        while(hh<tt&&slope(q[tt],q[tt-1])<slope(i,q[tt-1])) tt--;
        // while(hh<tt&&check(get(q[tt],q[tt-1]),get(i,q[tt-1]))) tt--;
        q[++tt]=i;
    }
}
int main() {
    scanf("%d%d",&n,&k);
    ld l=-1e6,r=1e6;
    while(l+(1e-20)<r) {
        ld mid=(l+r)/2;
        calc(mid);
        if(f[0].k<=k) l=mid;// 需要进行更多轮 每轮的奖金需要增加
        else r=mid;
    }
    calc(l);
    printf("%.9Lf\n",f[0].v-f[0].k*l);
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<ld,int> pdi;
#define x first 
#define y second
const int N=100010;
int n,k;
struct node {
    ld v;
    int k;
}f[N];
int q[N],hh=0,tt=-1;
inline ld val(int i,int j,ld d) {
    return f[j].v+d+1-1.0*i/j;
}
inline pdi get(int i,int j) {
    return {(1.0/i-1.0/j),f[i].v-f[j].v};
}
inline bool check(pdi a,pdi b) {
    return a.x*b.y>a.y*b.x;
}
inline void calc(ld d) {
    hh=0,tt=-1;
    f[n]={0.0,0}; 
    q[++tt]=n;
    for(int i=n-1;i>=0;i--) {
        
        while(hh<tt&&val(i,q[hh+1],d)>val(i,q[hh],d)) hh++;
        f[i].v=val(i,q[hh],d),f[i].k=f[q[hh]].k+1;
        while(hh<tt&&check(get(q[tt],q[tt-1]),get(i,q[tt-1]))) tt--;
        q[++tt]=i;
    }
}
int main() {
    scanf("%d%d",&n,&k);
    ld l=-1e6,r=1e6;
    while(l+(1e-20)<r) {
        ld mid=(l+r)/2;
        calc(mid);
        if(f[0].k<=k) l=mid;// 需要进行更多轮 每轮的奖金需要增加
        else r=mid;
    }
    calc(l);
    printf("%.9Lf\n",f[0].v-f[0].k*l);
    return 0;
}