锯木厂选址

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1862 字
山路上n棵树，在树的位置新建两个锯木厂，木材
一本通
练习
正文

/*
原题：T1614「一本通 5.6 练习 5」锯木厂选址（CEOI 2004）
题意：山路上 n 棵树，在树的位置新建两个锯木厂，木材只能朝下运，最小化总运费（每公斤每米 1 分）。
思路：把 n 棵树按两个锯木厂位置 p<q 分成三段：1..p 运到 p，p+1..q 运到 q，q+1..n 运到山脚。
设位置 p[i]、重量前缀和 sw、∑w[i]p[i]=sp；则总代价 C(p,q)=F[q]+sw[p]*p[p]-p[q]*sw[p]。
对每个 q 求 min_{p<q}，化为斜率优化：直线 m=-sw[p], b=sw[p]*p[p]，在 x=p[q] 处取最小值。
用单调斜率+单调查询的凸包（deque）维护，a,b 比较用 __int128 防爆。
复杂度：时间 O(n)，空间 O(n)
易错点：1) 运费按“朝下最近锯木厂”分段，不是任意最近；2) 数值可达 4e18 用 long long，交点比较用 __int128；3) 两段锯木厂位置均需在 1..n 内。
*/
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
struct Line{
    ll m,b;
    ll eval(ll x){ return m*x+b; }
};
deque<Line> dq;
// 去掉队尾无用直线：斜率递减、查询 x 递增时，若 l2 被 l1,l3 包住则弹出
bool bad(Line l1,Line l2,Line l3){
    __int128 left=(__int128)(l2.b-l1.b)*(l2.m-l3.m);
    __int128 right=(__int128)(l3.b-l2.b)*(l1.m-l2.m);
    return left>=right;
}
void addLine(Line l){
    while(dq.size()>=2 && bad(dq[dq.size()-2],dq.back(),l)) dq.pop_back();
    dq.push_back(l);
}
ll query(ll x){
    while(dq.size()>=2 && dq[0].eval(x) >= dq[1].eval(x)) dq.pop_front();
    return dq[0].eval(x);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    vector<ll> w(n+1),d(n+1);
    for(int i=1;i<=n;i++){
        cin>>w[i]>>d[i];
    }
    // p[i]: 第 i 棵树相对山顶的位置；山脚在 p[n+1]
    vector<ll> p(n+2,0);
    for(int i=2;i<=n+1;i++){
        p[i]=p[i-1]+d[i-1];
    }
    vector<ll> sw(n+1,0),sp(n+1,0);
    for(int i=1;i<=n;i++){
        sw[i]=sw[i-1]+w[i];
        sp[i]=sp[i-1]+(ll)w[i]*p[i];
    }
    ll foot=p[n+1];
    auto F=[&](int j)->ll{
        ll f=(ll)p[j]*sw[j]-sp[j];
        ll g=(ll)foot*(sw[n]-sw[j])-(sp[n]-sp[j]);
        return f+g;
    };
    ll ans=LLONG_MAX;
    for(int q=2;q<=n;q++){
        int pp=q-1;
        addLine({-sw[pp],(ll)sw[pp]*p[pp]});
        ll cost=F(q)+query(p[q]);
        if(cost<ans) ans=cost;
    }
    cout<<ans<<"\n";
    return 0;
}
锯木厂选址

正文

一本通·提高篇的其它内容
