题目链接：https://codeforces.com/problemset/problem/1852/C
题意：
给定一个长度为n的序列和正整数k；
每次可以选取任意一个区间，将区间内每个数减1；
如果出现一个数变成0，那么那个数变成k；
问至少操作多少次可以使得每个数变成k；
分析：
将每个数值抽象为对应高度的矩形（k 看作 0）并按索引排列在一起，假设数字变为 0 后变成 k，目标就变为了“将所有数字变为 0”，那么总操作数为所有相邻矩形高度上升的总和。
例如：1 2 3 4 在k为5的时候，操作次数为4，1 2 3 4 1 2 在k为5 的时候操作次数为4 + 2 = 6；
那么我们现在就需要分析如何将这个操作次数进行减少；
我们将“高度变为0后转变为k”这个条件替换成增加k（可以看出是等价的）；
那么我们可以进行如下操作：
假设已经确定了i个的操作次数，那么现在考虑第i+1个，设第i+1个的高度为h【i+1】，那么
1：h【i+1】<=h【i】，不进行任何操作；
2：h【i+1】>h【i】：
a：不增加k，将答案增加h【i+1】-h【i】；
b：选择一个j<=i,使得 k + h【j】 - h【j-1】 - max（0，h【j】-h【j-1】）这个值最小为 f【i】，并将 j 到 i中的高度都增加 k ，然后答案增加 f【i】；
在 a 和 b内选择增加最小的一种方案；
但是这个复杂度是O（n^2)是无法通过此题的，考虑单调队列优化；
每个f【i】最多被选择一次，故复杂度是O（nlogn）；
代码：
#include<bits/stdc++.h> #define int long long signed main() { std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0); int T; std::cin >> T; while (T--) { int n, k; std::cin >> n >> k; std::vector<int> a(n + 1, 0); for (int i = 1; i <= n; ++i)std::cin >> a[i], a[i] %= k; std::priority_queue<int, std::vector<int>, std::greater<int> > Q; int ans = 0; for (int i = 1; i <= n; ++i) { if (a[i] == a[i - 1])continue; if (a[i] < a[i - 1])Q.push(k + a[i] - a[i - 1]); else Q.push(a[i] - a[i - 1]), ans += Q.top(), Q.pop(); } std::cout << ans << "\n"; } return 0; }
使用单调队列来优化是反悔贪心比较常见的方法，读者感兴趣可以去了解一下：）