C++ 优化代码：最小代价改变数字 | 详细注释

#include<bits/stdc++.h> using namespace std; const int N = 2e5+10; #define rep(i,l,r) for(int i = l;i <= r;i++) #define ll long long //#define db double

ll n,m,dp[N],h[N],cn[N]; stackq1;

struct node{ ll b,x; };

// 计算在给定的 t 值下，最小的代价以及需要改变的次数 node ck(ll t){ while(!q1.empty()) q1.pop(); q1.push(1); rep(i,2,n){ dp[i] = dp[i-1] + abs(h[i]-h[i-1]); cn[i] = cn[i-1]; while(!q1.empty()){ ll k1 = dp[q1.top()] + abs(h[q1.top()]-h[i]) - t; if(k1 == dp[i]){ cn[i] = min(cn[i], cn[q1.top()]+1); } if(k1 < dp[i]){ dp[i] = k1; cn[i] = cn[q1.top()] + 1; } if(h[q1.top()] >= h[i]){ break; } q1.pop(); } q1.push(i); } return {dp[n], cn[n]}; }

// 二分法确定最小的 t 值 void erfen(ll l,ll r,ll x){ while(l < r){ ll mid = l + (r-l+1)/2 - 1; if(ck(mid).x >= x){ r = mid; } else{ l = mid + 1; } } cout << r*x + ck(r).b << '\n'; // 此时 r 为 k }

int main(){ ios::sync_with_stdio(0); cin.tie(0), cout.tie(0);

cin >> n >> m;
rep(i,1,n) cin >> h[i];

if(ck(0).x <= m){
    cout << ck(0).b << '\n'; // k 为 0
}
else{
    erfen(-1e16, 1e16, m);
}
return 0;

}