第十一届中国大学生程序设计竞赛网络预选赛（CCPC Online 2025）——造桥与砍树 · znzryb
## 思路讲解
[https://chatgpt.com/share/68cf5c55-f5c8-8013-b94f-360aabb163b8](https://chatgpt.com/share/68cf5c55-f5c8-8013-b94f-360aabb163b8)
这道题目就是懒更新，一般来说，塞进懒更新库的是比较乐观的估计，或者说是比较好的估计。
```cpp
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](https://qoj.ac/submission/1381898)
::: 源代码
```cpp
// 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";
*/
```
:::
::: 可解释性代码程序
```cpp
#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……）