问题描述题目给定序列 a进行 k 次操作每次把最大的数变最小的或把最小的变成最大的求序列的最小极差。 核心思路如果暴力每次枚举两种情况会爆 (2^N)。其次可以证明任意操作序列都可以等价地调整为先进行 i 次「最小 → 最大」再进行 j 次「最大 → 最小」或反过来。因此只需考虑两种操作顺序。固然要排序那么情况就只有两种第一种先进行 i 次把最小的变成最大的再进行 j 次把最大的变成最小的。第二种先进行 j 次把最大的变成最小的再进行 i 次把最小的变成最大的。设操作最后得到的极差为 a[r] - a[l]l 和 r 如何确定 第一种先进行 i 次 最小 → 最大数组多了 i 个最大值再进行 j 次 最大 → 最小如果 j ≤ i只会消掉这 i 个新增的最大值中的 j 个最大值仍是 a[n-1]如果 j i会消掉所有新增最大值 原本的最大值所以最大值向左移动 j-i 位所以 r n-1 - max(0, j-i) 则第二种l max(0, i-j);r n-1 - j;故对 i 进行遍历0-k每次遍历讨论两种操作模式取较小值即可代码实现完整代码#include bits/stdc.h #define all(a) a.begin(),a.end() #define rall(a) a.rbegin(),a.rend() #define LL long long #define MAX INT_MAX #define LMAX LLONG_MAX #define rep(i,a,b) for(int i(int)a;iint(b);i) using namespace std; void solve(){ int n,k; cinnk; vectorinta(n); rep(i,0,n) cina[i]; sort(all(a)); //特判 if(kn-1){ cout0\n; return; } LL ansa[n-1]-a[0]; rep(i,0,k1){ int jk-i; int li; int rn-1-max(0,j-i); if(lr) ansmin(ans,(LL)a[r]-a[l]); else {ans0;break;} lmax(0,i-j); rn-1-j; if(lr) ansmin(ans,(LL)a[r]-a[l]); else {ans0;break;} } coutans\n; } int main(){ ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); int tc1; //cintc; while(tc--){solve();}return 0;}## 复杂度分析 排序O(n log n) 枚举 iO(k) 总复杂度O(n log n k)等价于 O(n log n) ## 总结 本题关键在于两个转化 1. 操作顺序可以重排为“先一类再另一类”