传智杯 初赛 D-莲子的物理热力学
题目背景
莲子正在研究分子的运动。
每个分子都有一个速度,约定正方向为正,负方向为负。分子的数量极多,速度又并不一致,看上去杂乱无章。于是莲子希望调整部分分子的速度,使得最终分子们看上去整齐。
题目描述
莲子给定了 $n$ 个整数 $a_1,a_2,\cdots a_n$,描述每个分子。现在她可以进行至多 $m$ 次操作(也可以一次也不进行),每次操作可以执行以下两条之一:
- 选择 $i$,满足 $a_i=\min_j\{a_j\}$,然后将 $a_i$ 变为 $\max_j\{a_j\}$。
- 选择 $i$,满足 $a_i=\max_j\{a_j\}$,然后将 $a_i$ 变为 $\min_j\{a_j\}$。
现在莲子希望需要最小化最终序列的极差(最大值减去最小值的差)。请求出最小的极差。
例如,对于序列 $a=\{5,1,4\}$,可以进行如下几次操作:
- 选择 $i=1$,满足 $a_1=5$ 是当前的最大值 $5$,可以将 $a_1$ 修改成当前的最小值 $1$,此时序列变成 $\{1,1,4\}$;
- 再选 $i=2$,满足 $a_2=1$ 是当前的最小值 $1$,可以将 $a_2$ 修改成当前的最大值 $4$,此时序列变成 $\{1,4,4\}$。
这两次操作后得到的序列为 $\{1,4,4\}$。最大值减去最小值的差为 $|4-1|=3$。
当然,这种操作方式得到的极差并非最小。最优策略是,先将最大值 $a_1=5$ 变成目前的最小值 $1$,再把此时的最大值 $a_3=4$ 变成目前的最小值 $1$。此时序列为 $\{1,1,1\}$,得到的极差 $|1-1|=0$ 是所有策略中最小的。
输入格式
- 第一行有两个正整数 $n,m$,分别表示序列的长度和你最多可以进行的操作次数。
- 第二行有 $n$ 个整数 $a$,描述给定的序列。
输出格式
- 输出共一行一个整数,表示最优策略下能得到的最小极差。
样例 #1
样例输入 #1
3 2
5 1 4
样例输出 #1
0
样例 #2
样例输入 #2
8 0
1 2 3 4 5 6 7 8
样例输出 #2
7
样例 #3
样例输入 #3
8 3
1 5 5 5 6 6 9 10
样例输出 #3
4
提示
样例解释
样例 $1$:$\{5,1,4\}\to\{1,1,4\}\to\{1,1,1\}$,极差为 $0$。
样例 $2$:$\{1,2,3,4,5,6,7,8\}$,什么也做不了,极差为 $7$。
样例 $3$:$\{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\}$,极差为 $4$。
数据范围及约定
对于全部数据,保证 $1\le n \le 10^5$,$0\le m\le10^9$,$|a_i|\le 10^9$。
题解
贪心题。
假设 m 次操作后,剩下来的数字的值域为 [l,r]。那么原来 a 数列里,所有严格小于 l 的数字肯定都被操作了,同时所有严格大于 r 的数字肯定也被操作了。
设 a 里面一共有 u 个数严格小于 l;有 v 个数严格大于 r。
断言:所需要的操作次数至少为 u+v+min(u,v),并且可以取到。
证明:如果一个位置在操作后,它的值还在 [l,r] 之外,那么后面某个时候肯定还要把它进行操作。容易发现,至少前 min(u,v) 次操作肯定都无法让结果变到 [l,r] 内。因此执行完这至少 min(u,v) 次操作后肯定还要再把这 u+v 个数都操作一遍,这是容易做到的(通过 min(u,v) 次操作,你总能把此时值域的下界提升到 l 或者把上界降低到 r)。所以最优决策肯定不会小于 u+v+min(u,v) 次。
那么这题怎么做呢?
直接将 a 数组从小到大排序。考虑枚举 l=ai,计算出最小的 r=aj,一定有(i−1)+(n−j)+min(i−1,n−j)≤m。容易发现随着 i 的增大,j 肯定是单调不减的。因此首先预处理j=1,接着随着 i 的增大找到可以满足条件的最小的 j。显然当i>min(n,m+1) 时就不存在这样的 j 了。
时间复杂度为 O(nlogn),瓶颈在于排序。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int a[N];
//不能用0x3f3f3f3f
int ans = 2147483647;
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + n + 1);
int j = 1, end = min(n, m + 1);
for (int i = 1; i <= end; i++)
{
j = max(i, j);
while ((i - 1) + (n - j) + min(i - 1, n - j) > m)
j++;
ans = min(ans, a[j] - a[i]);
}
cout << ans;
}
学长,为啥不能0x3f3f3f3f
操作后,最大值减最小值,差有可能比0x3f3f3f3f大