U535992 J-C 小梦的宝石收集

问题描述

题目

给定序列 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;i<int(b);++i) using namespace std; void solve(){ int n,k; cin>>n>>k; vector<int>a(n); rep(i,0,n) cin>>a[i]; sort(all(a)); //特判： if(k>=n-1){ cout<<"0\n"; return; } LL ans=a[n-1]-a[0]; rep(i,0,k+1){ int j=k-i; int l=i; int r=n-1-max(0,j-i); if(l<=r) ans=min(ans,(LL)a[r]-a[l]); else {ans=0;break;} l=max(0,i-j); r=n-1-j; if(l<=r) ans=min(ans,(LL)a[r]-a[l]); else {ans=0;break;} } cout<<ans<<'\n'; } int main(){ ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); int tc=1; //cin>>tc; while(tc--){

solve();
}
return 0;
}

## 复杂度分析 排序：O(n log n) 枚举 i：O(k) 总复杂度：O(n log n + k)等价于 O(n log n) ## 🎯 总结 本题关键在于两个转化： 1. 操作顺序可以重排为“先一类再另一类”