第十一届中国大学生程序设计竞赛网络预选赛（CCPC Online 2025）——造桥与砍树

思路讲解

https://chatgpt.com/share/68cf5c55-f5c8-8013-b94f-360aabb163b8

这道题目就是懒更新，一般来说，塞进懒更新库的是比较乐观的估计，或者说是比较好的估计。

priority_queue<Val> pq;
multiset<ll> s{A[0]}, rem(A.begin() + 1, A.end());
ll ans = 0;
auto add = [&](ll x) {
    auto it = rem.lower_bound(K-x);
    if (it == rem.end())
        return;
    pq.push({x, x + *it - K});
};
auto find = [&](ll x) {
    auto it = rem.lower_bound(K - x);
    if (it == rem.end())
        return INF;
    return *it;
};
auto get = [&]() {
    while (!pq.empty()) {
        auto [val, res] = pq.top();
        ll node = find(val);
        ll lres = node + val - K;
        if (lres == res) {
            return (pll){res, node};
        } else {
            pq.pop();
            pq.push({val, lres});
        }
    }
    return (pll){INF, INF};
};
add(A[0]);
FOR(i, 2, N) {
    ll lans = *s.begin() + *rem.begin();
    auto [res, node] = get();
    if (res < lans) {
        lans = res;
        s.insert(node);
        rem.erase(rem.find(node));
        add(node);
    } else {
        ll node=*rem.begin();
        s.insert(node);
        rem.erase(rem.begin());
        add(node);
    }
    ans += lans;
}

AC代码

https://qoj.ac/submission/1381898

源代码

// by Gospel_rock
#include <algorithm>
#include <bits/stdc++.h>
#include <functional>
#include <queue>
#include <vector>
#define all(vec) vec.begin(), vec.end()
#define PB push_back
#define PF push_front
#define EB emplace_back
#define EF emplace_front
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define lson(o) (o << 1)
#define rson(o) (o << 1 | 1)
#define SZ(a) ((long long)a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var << ":" << var << "\n";
#define cend cerr << "\n-----------\n"
#define fsp(x) fixed << setprecision(x)
#define minn(vec) *min_element(vec.begin(), vec.end())
#define maxx(vec) *max_element(vec.begin(), vec.end())

using namespace std;
#ifdef LOCAL
template <typename T> void _print(T x) { cerr << x; }
// 可以打印多层数组，但是格式不是很好
template <typename T> void _print(vector<T> v) {
    cerr << "[ ";
    for (T i : v)
        _print(i), cerr << " ";
    cerr << "]";
}
template <typename T> void _print(set<T> s) {
    cerr << "{ ";
    for (T i : s)
        _print(i), cerr << " ";
    cerr << "}";
}
template <typename T, typename U> void _print(pair<T, U> p) {
    cerr << "{";
    _print(p.first);
    cerr << ", ";
    _print(p.second);
    cerr << "}";
}
template <typename T, typename U> void _print(map<T, U> m) {
    cerr << "{ ";
    for (auto &p : m)
        _print(p), cerr << " ";
    cerr << "}";
}
// 打印两层数组，格式好一些
template <typename T> void _print(vector<vector<T>> v) {
    cerr << "{\n";
    for (auto i : v)
        _print(i), cerr << "\n";
    cerr << " }";
}
#endif

using ll = long long;
using ull = unsigned long long;
using ld = double;
using LD = long double;
using i128 = __int128;
using pdd = pair<ld, ld>;
using plb = pair<ll, bool>;
using pll = pair<ll, ll>;
using vll = vector<ll>;
using vb = vector<bool>;
using tll = tuple<ll, ll, ll>;
using vii = vector<int>;
using vpll = vector<pll>;
using vtll = vector<tll>;
using vdb = vector<ld>;
using vc = vector<char>;
using arr3 = array<ll, 3>;
using arr2 = array<ll, 2>;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6 + 10,
                    INF = (ll)1e17 + 3; // 1e17+3是素数 1e18+9是素数
static constexpr ll mod = (ll)1e9 + 7;  // 998244353;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll N, M, Q, X, K, T, lT;

inline void __();
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> lT;
    while (lT--)
        __();
    return 0;
}
/*
那么其实这道题目采用的是懒惰更新策略

*/
struct Val {
    ll a, res;
    bool operator<(const Val &o) const { return res > o.res; }
};
inline void __() {
    cin >> N >> K;
    vll A(N);
    FOR(i, 1, N) {
        cin >> A[i - 1];
        A[i - 1] %= K;
    }
    // sort(all(A));
    priority_queue<Val> pq;
    multiset<ll> s{A[0]}, rem(A.begin() + 1, A.end());
    ll ans = 0;
    auto add = [&](ll x) {
        auto it = rem.lower_bound(K-x);
        if (it == rem.end())
            return;
        pq.push({x, x + *it - K});
    };
    auto find = [&](ll x) {
        auto it = rem.lower_bound(K - x);
        if (it == rem.end())
            return INF;
        return *it;
    };
    auto get = [&]() {
        while (!pq.empty()) {
            auto [val, res] = pq.top();
            ll node = find(val);
            ll lres = node + val - K;
            if (lres == res) {
                return (pll){res, node};
            } else {
                pq.pop();
                pq.push({val, lres});
            }
        }
        return (pll){INF, INF};
    };
    add(A[0]);
    FOR(i, 2, N) {
        ll lans = *s.begin() + *rem.begin();
        auto [res, node] = get();
        if (res < lans) {
            lans = res;
            s.insert(node);
            rem.erase(rem.find(node));
            add(node);
        } else {
            ll node=*rem.begin();
            s.insert(node);
            rem.erase(rem.begin());
            add(node);
        }
        ans += lans;
#ifdef LOCAL
    debug(i);
    debug(lans);
    debug(res);
#endif
    }
    cout << ans << "\n";
}
/*
AC
https://qoj.ac/submission/1381898


priority_queue<Val> best;
    FOR(i,1,N){
        ll a=A[i-1];
        auto it=lower_bound(all(A),K-a);
        if(it==A.end()) continue;
        ll lans=*it+a-K;
        best.push({a,lans});
    }
    multiset<ll> s{A[0]},rem(A.begin()+1,A.end());
auto cal=[&](ll a){
        auto it=s.lower_bound(K-a);
        if(it==s.end()) return -1ll;
        ll lans=*it+a-K;
        return lans;
    };
    auto get=[&](){
        while (!best.empty()) {
            auto[val,res]=best.top();
            ll lres=cal(val);
            if(lres==res){
                return res;
            }else{

            }
        }
    };
    while (!rem.empty()) {

    }


 // multiset<ll> s={A[1]};
    // priority_queue<ll,vector<ll>,greater<> > rem;
    // FOR(i,2,N){
    //     rem.push(A[i]);
    // }
    // ll ans=0;
    // while (!rem.empty()) {
    //     auto a=rem.top();
    //     rem.pop();
    //     ll lans=INF;
    //     if(*s.begin()+a<K){
    //         lans=*s.begin()+a;
    //     }
    //     auto it=s.lower_bound(K-a);
    //     if(it!=s.end()){
    //         lans=min(lans,*it+a-K);
    //     }
    //     s.insert(a);
    //     ans+=lans;
    // }
    // cout<<ans<<"\n";
*/

可解释性代码程序

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

using i64 = long long;
const i64 INF = (1LL << 62);

/*
 * 可解释性版本说明：
 * - VERBOSE=true：打印每一步（推荐小样本学习）
 * - VERBOSE=false：只打印答案（适合大数据）
 */
static bool VERBOSE = true;

/* 小根堆元素：value为缓存的 h(t)-t，下界（可能过期但绝不偏大）；t=K-y（不取模） */
struct WrapItem {
    i64 val;
    i64 t;
    bool operator>(const WrapItem& o) const {
        if (val != o.val) return val > o.val;
        return t > o.t;
    }
    bool operator<(const WrapItem& o) const {
        if (val != o.val) return val < o.val;
        return t < o.t;
    }
};

/* 打印工具 */
template<class T>
static void print_multiset(const multiset<T>& S, const string& name) {
    cout << name << " = {";
    bool first = true;
    for (auto &x : S) { if (!first) cout << " "; cout << x; first=false; }
    cout << "}\n";
}
static void print_heap_copy(priority_queue<WrapItem, vector<WrapItem>, greater<WrapItem>> pq, const string& name) {
    cout << name << " = [ ";
    while(!pq.empty()){
        auto it = pq.top(); pq.pop();
        cout << "(" << it.val << "," << it.t << ") ";
    }
    cout << "]\n";
}

/* 主解法：带“懒刷新”的越界候选 + 不越界候选，逐日连接 n-1 次 */
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    if(!(cin >> T)) return 0;

    for(int tc=1; tc<=T; ++tc){
        int n; i64 K;
        cin >> n >> K;
        vector<i64> t(n);
        for(int i=0;i<n;i++) cin >> t[i];

        // 快速边界：n<=1 或 K==1 → 每日浪费必为0
        if(n<=1 || K==1){
            if (VERBOSE) {
                cout << "Case #" << tc << "（n="<<n<<", K="<<K<<"）：\n";
                cout << "  边界情形：总浪费 = 0\n\n";
            } else {
                cout << 0 << "\n";
            }
            continue;
        }

        // 取残余 r[i] = t[i] % K
        vector<i64> r(n);
        for(int i=0;i<n;i++) r[i] = t[i] % K;

        // S：已接入父亲残余，初始只有 r[0]
        // B：未接入孩子残余，初始为 r[1..n-1]
        multiset<i64> S, B;
        S.insert(r[0]);
        for(int i=1;i<n;i++) B.insert(r[i]);

        // h(t)：在B中找 >= t 的最小元素。不存在返回 INF
        auto h_of = [&](i64 t)->i64{
            auto it = B.lower_bound(t);
            return (it==B.end()? INF : *it);
        };

        // 小根堆pq：维护所有父亲阈值 t 的当前“下界值” h(t)-t
        priority_queue<WrapItem, vector<WrapItem>, greater<WrapItem>> pq;

        // 把 t 的当前“下界值”入堆（若B中存在可配孩子）
        auto try_push_t = [&](i64 t){
            // t = K - y，y∈[0..K-1] → t∈[1..K]；当 y==0 → t==K → B中通常无>=K的孩子（不入堆即可）
            if(t < 1 || t > K) return;
            i64 hx = h_of(t);
            if(hx != INF) pq.push(WrapItem{hx - t, t});
        };

        // 初始化：对当前S的每个父亲 y，推入 t=K-y
        for(i64 y : S){
            i64 t0 = K - y; // 不取模！
            try_push_t(t0);
        }

        // 懒刷新堆顶：返回（真实的越界最优代价, 对应的t）
        auto best_wrap = [&](int day)->pair<i64,i64>{
            while(!pq.empty()){
                auto top = pq.top();
                i64 tcur = top.t;
                i64 hx   = h_of(tcur);
                i64 real = (hx==INF? INF : (hx - tcur));
                if(real != top.val){
                    if(VERBOSE){
                        cout << "    [懒刷新] 堆顶过期: 旧("<<top.val<<","<<tcur<<") "
                             << "→ 现real=" << (real==INF? -1:real) << "\n";
                    }
                    pq.pop();
                    if(real != INF){
                        pq.push(WrapItem{real, tcur});
                        if(VERBOSE){
                            cout << "    [懒刷新] 回填新项: ("<<real<<","<<tcur<<")\n";
                        }
                    }
                }else{
                    if(VERBOSE){
                        cout << "    [懒刷新] 堆顶新鲜: ("<<real<<","<<tcur<<") 为当前全局最小越界\n";
                    }
                    return {real, tcur};
                }
            }
            if(VERBOSE){
                cout << "    [懒刷新] 堆为空：无越界候选\n";
            }
            return {INF, -1};
        };

        __int128 total_waste = 0;

        if(VERBOSE){
            cout << "Case #" << tc << "（n="<<n<<", K="<<K<<"）\n";
            cout << "初始状态：\n";
            print_multiset(S, "  S(父亲残余)");
            print_multiset(B, "  B(孩子残余)");
            print_heap_copy(pq, "  pq(下界堆,val=t候选的h(t)-t)");
            cout << "\n";
        }

        for(int day=1; day<=n-1; ++day){
            if(VERBOSE) {
                cout << "—— 第 " << day << " 天 ——\n";
                print_multiset(S, "  当前S");
                print_multiset(B, "  当前B");
                print_heap_copy(pq, "  当前pq");
            }

            // 1) 越界候选：懒刷新堆顶到新鲜，得到真实的最小越界代价
            auto [wrap_cost, wrap_t] = best_wrap(day);

            // 2) 不越界候选：仅当 minS + minB < K 时有效
            i64 plain_cost = INF, plain_x = -1;
            if(!B.empty()){
                i64 a = *S.begin();  // min S
                i64 b = *B.begin();  // min B
                if(a + b < K){
                    plain_cost = a + b;
                    plain_x = b;
                }
            }
            if(VERBOSE){
                cout << "  候选对比：\n";
                cout << "    越界候选 = " << (wrap_cost==INF? -1:wrap_cost)
                     << "  (t=" << wrap_t << ")\n";
                cout << "    不越界候选 = " << (plain_cost==INF? -1:plain_cost) << "\n";
            }

            bool use_wrap = (wrap_cost <= plain_cost);
            if(use_wrap){
                // 选择越界：真实对应孩子 x = h(wrap_t)
                auto itx = B.lower_bound(wrap_t);
                // 一定存在，因为 wrap_cost != INF
                i64 x = *itx;
                total_waste += (x - wrap_t);

                if(VERBOSE){
                    cout << "  [决策] 选择【越界】 x="<<x<<"（来自 h(t), t="<<wrap_t<<"），"
                         << "当日浪费 = "<< (x - wrap_t) << "\n";
                }

                // 更新集合
                B.erase(itx);
                S.insert(x);

                // 新父亲产生的新阈值 t' = K - x（x==0 → t'=K，一般无候选，不入堆亦可）
                i64 t_new = K - x;
                try_push_t(t_new);

            }else{
                // 选择不越界：取 minB
                i64 x = plain_x;  // 已保证有效
                total_waste += plain_cost;

                if(VERBOSE){
                    i64 a = *S.begin();
                    cout << "  [决策] 选择【不越界】 x="<<x<<"（与 a=minS="<<a<<" 配对），"
                         << "当日浪费 = "<< plain_cost << "（因 a+x<"<<K<<"）\n";
                }

                // 更新集合
                B.erase(B.begin());
                S.insert(x);

                // 新父亲阈值
                i64 t_new = K - x;
                try_push_t(t_new);
            }

            if(VERBOSE){
                print_multiset(S, "  更新后S");
                print_multiset(B, "  更新后B");
                print_heap_copy(pq, "  更新后pq");
                cout << "\n";
            }
        }

        long long ans_ll = (long long)total_waste;
        if(VERBOSE){
            cout << "==> Case #" << tc << " 的最小总浪费 = " << ans_ll << "\n\n";
        }else{
            cout << ans_ll << "\n";
        }
    }

    return 0;
}
/*
Case #1（n=5, K=3）
初始状态：
  S(父亲残余) = {1}
  B(孩子残余) = {0 1 2 2}
  pq(下界堆,val=t候选的h(t)-t) = [ (0,2) ]

—— 第 1 天 ——
  当前S = {1}
  当前B = {0 1 2 2}
  当前pq = [ (0,2) ]
    [懒刷新] 堆顶新鲜: (0,2) 为当前全局最小越界
  候选对比：
    越界候选 = 0  (t=2)
    不越界候选 = 1
  [决策] 选择【越界】 x=2（来自 h(t), t=2），当日浪费 = 0
  更新后S = {1 2}
  更新后B = {0 1 2}
  更新后pq = [ (0,1) (0,2) ]

—— 第 2 天 ——
  当前S = {1 2}
  当前B = {0 1 2}
  当前pq = [ (0,1) (0,2) ]
    [懒刷新] 堆顶新鲜: (0,1) 为当前全局最小越界
  候选对比：
    越界候选 = 0  (t=1)
    不越界候选 = 1
  [决策] 选择【越界】 x=1（来自 h(t), t=1），当日浪费 = 0
  更新后S = {1 1 2}
  更新后B = {0 2}
  更新后pq = [ (0,1) (0,2) (0,2) ]

—— 第 3 天 ——
  当前S = {1 1 2}
  当前B = {0 2}
  当前pq = [ (0,1) (0,2) (0,2) ]
    [懒刷新] 堆顶过期: 旧(0,1) → 现real=1
    [懒刷新] 回填新项: (1,1)
    [懒刷新] 堆顶新鲜: (0,2) 为当前全局最小越界
  候选对比：
    越界候选 = 0  (t=2)
    不越界候选 = 1
  [决策] 选择【越界】 x=2（来自 h(t), t=2），当日浪费 = 0
  更新后S = {1 1 2 2}
  更新后B = {0}
  更新后pq = [ (0,2) (0,2) (1,1) ]

—— 第 4 天 ——
  当前S = {1 1 2 2}
  当前B = {0}
  当前pq = [ (0,2) (0,2) (1,1) ]
    [懒刷新] 堆顶过期: 旧(0,2) → 现real=-1
    [懒刷新] 堆顶过期: 旧(0,2) → 现real=-1
    [懒刷新] 堆顶过期: 旧(1,1) → 现real=-1
    [懒刷新] 堆为空：无越界候选
  候选对比：
    越界候选 = -1  (t=-1)
    不越界候选 = 1
  [决策] 选择【不越界】 x=0（与 a=minS=1 配对），当日浪费 = 1（因 a+x<3）
  更新后S = {0 1 1 2 2}
  更新后B = {}
  更新后pq = [ ]

==> Case #1 的最小总浪费 = 1

Case #2（n=8, K=7）
初始状态：
  S(父亲残余) = {3}
  B(孩子残余) = {1 1 2 2 4 5 6}
  pq(下界堆,val=t候选的h(t)-t) = [ (0,4) ]

—— 第 1 天 ——
  当前S = {3}
  当前B = {1 1 2 2 4 5 6}
  当前pq = [ (0,4) ]
    [懒刷新] 堆顶新鲜: (0,4) 为当前全局最小越界
  候选对比：
    越界候选 = 0  (t=4)
    不越界候选 = 4
  [决策] 选择【越界】 x=4（来自 h(t), t=4），当日浪费 = 0
  更新后S = {3 4}
  更新后B = {1 1 2 2 5 6}
  更新后pq = [ (0,4) (2,3) ]

—— 第 2 天 ——
  当前S = {3 4}
  当前B = {1 1 2 2 5 6}
  当前pq = [ (0,4) (2,3) ]
    [懒刷新] 堆顶过期: 旧(0,4) → 现real=1
    [懒刷新] 回填新项: (1,4)
    [懒刷新] 堆顶新鲜: (1,4) 为当前全局最小越界
  候选对比：
    越界候选 = 1  (t=4)
    不越界候选 = 4
  [决策] 选择【越界】 x=5（来自 h(t), t=4），当日浪费 = 1
  更新后S = {3 4 5}
  更新后B = {1 1 2 2 6}
  更新后pq = [ (0,2) (1,4) (2,3) ]

—— 第 3 天 ——
  当前S = {3 4 5}
  当前B = {1 1 2 2 6}
  当前pq = [ (0,2) (1,4) (2,3) ]
    [懒刷新] 堆顶新鲜: (0,2) 为当前全局最小越界
  候选对比：
    越界候选 = 0  (t=2)
    不越界候选 = 4
  [决策] 选择【越界】 x=2（来自 h(t), t=2），当日浪费 = 0
  更新后S = {2 3 4 5}
  更新后B = {1 1 2 6}
  更新后pq = [ (0,2) (1,4) (1,5) (2,3) ]

—— 第 4 天 ——
  当前S = {2 3 4 5}
  当前B = {1 1 2 6}
  当前pq = [ (0,2) (1,4) (1,5) (2,3) ]
    [懒刷新] 堆顶新鲜: (0,2) 为当前全局最小越界
  候选对比：
    越界候选 = 0  (t=2)
    不越界候选 = 3
  [决策] 选择【越界】 x=2（来自 h(t), t=2），当日浪费 = 0
  更新后S = {2 2 3 4 5}
  更新后B = {1 1 6}
  更新后pq = [ (0,2) (1,4) (1,5) (1,5) (2,3) ]

—— 第 5 天 ——
  当前S = {2 2 3 4 5}
  当前B = {1 1 6}
  当前pq = [ (0,2) (1,4) (1,5) (1,5) (2,3) ]
    [懒刷新] 堆顶过期: 旧(0,2) → 现real=4
    [懒刷新] 回填新项: (4,2)
    [懒刷新] 堆顶过期: 旧(1,4) → 现real=2
    [懒刷新] 回填新项: (2,4)
    [懒刷新] 堆顶新鲜: (1,5) 为当前全局最小越界
  候选对比：
    越界候选 = 1  (t=5)
    不越界候选 = 3
  [决策] 选择【越界】 x=6（来自 h(t), t=5），当日浪费 = 1
  更新后S = {2 2 3 4 5 6}
  更新后B = {1 1}
  更新后pq = [ (0,1) (1,5) (1,5) (2,3) (2,4) (4,2) ]

—— 第 6 天 ——
  当前S = {2 2 3 4 5 6}
  当前B = {1 1}
  当前pq = [ (0,1) (1,5) (1,5) (2,3) (2,4) (4,2) ]
    [懒刷新] 堆顶新鲜: (0,1) 为当前全局最小越界
  候选对比：
    越界候选 = 0  (t=1)
    不越界候选 = 3
  [决策] 选择【越界】 x=1（来自 h(t), t=1），当日浪费 = 0
  更新后S = {1 2 2 3 4 5 6}
  更新后B = {1}
  更新后pq = [ (0,1) (1,5) (1,5) (2,3) (2,4) (4,2) ]

—— 第 7 天 ——
  当前S = {1 2 2 3 4 5 6}
  当前B = {1}
  当前pq = [ (0,1) (1,5) (1,5) (2,3) (2,4) (4,2) ]
    [懒刷新] 堆顶新鲜: (0,1) 为当前全局最小越界
  候选对比：
    越界候选 = 0  (t=1)
    不越界候选 = 2
  [决策] 选择【越界】 x=1（来自 h(t), t=1），当日浪费 = 0
  更新后S = {1 1 2 2 3 4 5 6}
  更新后B = {}
  更新后pq = [ (0,1) (1,5) (1,5) (2,3) (2,4) (4,2) ]

==> Case #2 的最小总浪费 = 2


*/

心路历程（WA，TLE，MLE……）