为什么用决策单调性二分队列错了, 求助
查看原帖
为什么用决策单调性二分队列错了, 求助
689146
mushezi楼主2024/7/20 16:44

代码如下,求助, 感谢

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 3e5 + 5;

struct Opt{
    int l, r, id;
};

ll c[N], t[N], s, f[N];
int n;

ll F(int i, int j){
    return (f[j] + t[i]*(c[i] - c[j]) + s*(c[n] - c[j]));
}

struct Que{
    Opt q[N];
    int l, r;

    void Clear(){
        l = 1, r = 1;
        q[1] = {1, n, 0};
    }

    void Insert(int id){
        while(l <= r && F(q[r].l, q[r].id) >= F(q[r].l, id)) r--;

        if(l > r){
            l = r = 1;
            q[1] = {1, n, id};
            return ;
        }

        int a = q[r].l, b = q[r].r, mid = 0, res = -1;
        while(a <= b){
            mid = (a + b) >> 1;
            if(F(mid, q[r].id) >= F(mid, id)) b = mid - 1, res = mid;
            else a = mid + 1;
        }

        q[r].r = res - 1;
        q[++r] = {res, n, id};
    }

    int Find(int pos){
        int a = l, b = r, mid, res = -1;

        while(a <= b){
            mid = (a + b) >> 1;
            if(q[mid].l <= pos) a = mid + 1, res = q[mid].id;
            else b = mid - 1;
        }

        return res;
    }
} q;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> s;
    for(int i = 1; i <= n; i++){
        cin >> t[i] >> c[i];
        t[i] += t[i - 1];
        c[i] += c[i - 1];
    }

    f[0] = 0;
    q.Clear();

    for(int i = 1; i <= n; i++){
        int cur = q.Find(i);
        f[i] = F(i, cur);
        q.Insert(i);
    }

    cout << f[n];
    
    return 0;
}

2024/7/20 16:44
加载中...