D-莲子的物理热力学

D-莲子的物理热力学

题目背景

莲子正在研究分子的运动。

每个分子都有一个速度，约定正方向为正，负方向为负。分子的数量极多，速度又并不一致，看上去杂乱无章。于是莲子希望调整部分分子的速度，使得最终分子们看上去整齐。

题目描述

莲子给定了 $n$ 个整数 $a_1,a_2,\cdots a_n$，描述每个分子。现在她可以进行至多 $m$ 次操作（也可以一次也不进行），每次操作可以执行以下两条之一：

• 选择 $i$，满足 a i = min ⁡ j { a j } a_i=\min_j\{a_j\} ai​=minj​{aj​}，然后将 $a_i$ 变为 max ⁡ j { a j } \max_j\{a_j\} maxj​{aj​}。
• 选择 $i$，满足 a i = max ⁡ j { a j } a_i=\max_j\{a_j\} ai​=maxj​{aj​}，然后将 $a_i$ 变为 min ⁡ j { a j } \min_j\{a_j\} minj​{aj​}。

现在莲子希望需要最小化最终序列的极差（最大值减去最小值的差）。请求出最小的极差。

---

例如，对于序列 a = { 5 , 1 , 4 } a=\{5,1,4\} a={5,1,4}，可以进行如下几次操作：

• 选择 $i=1$，满足 $a_1=5$ 是当前的最大值 $5$，可以将 $a_1$ 修改成当前的最小值 $1$，此时序列变成 { 1 , 1 , 4 } \{1,1,4\} {1,1,4}；
• 再选 $i=2$，满足 $a_2=1$ 是当前的最小值 $1$，可以将 $a_2$ 修改成当前的最大值 $4$，此时序列变成 { 1 , 4 , 4 } \{1,4,4\} {1,4,4}。

这两次操作后得到的序列为 { 1 , 4 , 4 } \{1,4,4\} {1,4,4}。最大值减去最小值的差为 $|4-1|=3$。

当然，这种操作方式得到的极差并非最小。最优策略是，先将最大值 $a_1=5$ 变成目前的最小值 $1$，再把此时的最大值 $a_3=4$ 变成目前的最小值 $1$。此时序列为 { 1 , 1 , 1 } \{1,1,1\} {1,1,1}，得到的极差 $|1-1|=0$ 是所有策略中最小的。

输入格式

• 第一行有两个正整数 $n,m$，分别表示序列的长度和你最多可以进行的操作次数。
• 第二行有 $n$ 个整数 $a$，描述给定的序列。

输出格式

• 输出共一行一个整数，表示最优策略下能得到的最小极差。

样例 #1

样例输入 #1

3 2
5 1 4
1
2

样例输出 #1

0
1

样例 #2

样例输入 #2

8 0
1 2 3 4 5 6 7 8
1
2

样例输出 #2

7
1

样例 #3

样例输入 #3

8 3
1 5 5 5 6 6 9 10
1
2

样例输出 #3

4
1

提示

样例解释

样例 $1$： { 5 , 1 , 4 } → { 1 , 1 , 4 } → { 1 , 1 , 1 } \{5,1,4\}\to\{1,1,4\}\to\{1,1,1\} {5,1,4}→{1,1,4}→{1,1,1}，极差为 $0$。
样例 $2$： { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 } \{1,2,3,4,5,6,7,8\} {1,2,3,4,5,6,7,8}，什么也做不了，极差为 $7$。
样例 $3$： { 1 , 5 , 5 , 5 , 6 , 6 , 9 , 10 } → { 10 , 5 , 5 , 5 , 6 , 6 , 9 , 10 } → { 5 , 5 , 5 , 5 , 6 , 6 , 9 , 10 } → { 5 , 5 , 5 , 5 , 6 , 6 , 9 , 5 } \{1,5,5,5,6,6,9,10\}\to\{10,5,5,5,6,6,9,10\}\to\{5,5,5,5,6,6,9,10\}\to\{5,5,5,5,6,6,9,5\} {1,5,5,5,6,6,9,10}→{10,5,5,5,6,6,9,10}→{5,5,5,5,6,6,9,10}→{5,5,5,5,6,6,9,5}，极差为 $4$。

数据范围及约定

对于全部数据，保证 $1\le n\le 10^5$，$0\le m\le 10^9$，$|a_i|\le 10^9$。

题解

#include
#include
using namespace std;
const int N = 1e5 + 10;
int num[N], n, m;

int main() {
    cin >> n >> m;
    for(int i = 0; i < n; i++ ) {
        cin >> num[i];
    }
    sort(num, num + n, [](int x, int y){return x < y;});
    int res = num[n - 1] - num[0];
    if(n > m) {
        for(int i = 0; i <= m / 2; i++ ) {
            int k = n - 1 - (m - i * 2);
            res = min(res, num[k] - num[i]);
        }
        for(int i = 0; i <= m/2 ; i++ ) {
            int k = (m - i * 2);
            res = min(res, num[n - 1 - i] - num[k]);
        }
    } else {
        res = 0;
    }
    cout << res << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28