1.29.codeforces div2 C,D 个人题解

C. Restricted Sorting

贪心

题目描述

给你一个长度为 \(n\) 的数组 \(a\)。对于一个整数 \(k\)，当且仅当可以通过执行以下操作任意次（包括零次）将 \(a\) 按非降序排序时，我们称它为“贪心的”(piggy)：
首先，选择两个下标 \(i\) 和 \(j\)（\(1 \leq i < j \leq n\)），使得 \(|a_i - a_j| \geq k\)；
然后，交换 \(a_i\) 和 \(a_j\)。
你需要找出最大的“贪心”整数 \(k\)。如果这样的整数不存在，输出 \(-1\)。
输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 \(t\)（\(1 \leq t \leq 10^4\)）。接下来是每个测试用例的描述。
每个测试用例的第一行包含一个整数 \(n\)（\(1 \leq n \leq 2 \cdot 10^5\)）——数组 \(a\) 的长度。
第二行包含 \(n\) 个整数 \(a_1, a_2, \dots, a_n\)（\(1 \leq a_i \leq 10^9\)）——数组 \(a\) 的元素。
保证所有测试用例的 \(n\) 之和不超过 \(2 \cdot 10^5\)。
输出格式

对于每个测试用例，输出一个整数——最大的“贪心”整数 \(k\)。
如果这样的整数不存在，输出 \(-1\)。
思路

原数组为\(a[N]\)，排序后为\(b[N]\)
如果\(a_{i}\)能够移动，那么必然存在一个\(a_{j}\)使得\(|a_{i}-a_{j}|\geq k\)，那么至少要有\(a_{i}-a_{min}\geq k\)或者\(a_{max}-a_{i}\geq k\)
若满足了上述两个条件之一，那么说明\(a_{i}\)一定可以与最大值或者最小值交换位置
那么所有满足上述条件的点所构成的位置集合\(S_{pos}\)，这些位置上的点可以通过与最大值最小值交换位置实现任意位置交换
对于\(a_{i}\neq b_{i}\)的点，必须满足\(a_{i}\)可移动且\(b_{i}\)可移动，才能在最终交换到正确位置上
因此，对于\(a_{i}\neq b_{i}\)的位置，可以计算出一个符合条件的最大\(k\)：

\[k=min(max(a-mi,ma-a),max(b-mi,ma-b))\]
对所有的\(k\)取最小值即可
代码

[code]#includeusing namespace std;#define ll long long#define int ll#define rep(i,a,b) for(int i=(a);i=(b);i--)#define ull unsigned long longvoid solve() {    int n;cin >> n;    vectora(n + 1);    vectorb(n + 1);    vectork(n + 1, 1e18);    int ma = 0, mi = 1e18;    rep(i, 1, n)cin >> a, b = a, ma = max(ma, a), mi = min(mi, a);    sort(b.begin() + 1, b.end());    bool dif = 0;int ans = 1e18;    rep(i, 1, n) {        if (a != b) {            int k = min(max(a - mi, ma - a), max(b - mi, ma - b));            dif = 1;            ans = min(ans, k);        }    }    if (!dif) {        cout  pos) & 1;    }    memset(vis, 0, sizeof(vis));    dfs(30, 0, 0);    int p = 0, q = 0;    int crp = 0, crq = 0;    per(pos, 30, 0) {        int idx = ch[pos][crp][crq];        int pbit = pp[idx], qbit = qq[idx];        if (pbit)p |= (1ll  ybit)crq = 2;        }    }    cout

这个有用。