Codeforces 1740C. Codeforces Round #831 (Div. 1 + Div. 2) C(思维+构造)
原题链接
简单
作者:
小小_88
,
2022-12-12 23:51:15
,
所有人可见
,
阅读 178
Bricks and Bags
C++ 代码
/*
本题要求选出三个价值为 w1, w2, w3 的物品,使得|w1 - w2| + |w2 - w3| 最小
我们先将整个序列排序,接下来在排序后的序列上进行分析
假设选出的价值为 w1, w2, w3 的物品下标分别是 p1, p2, p3
那么选出的三个物品的下标最多只有四种关系:
1. p1 < p2 < p3
2. p1 > p2 > p3
3. p2 < min(p1, p3)
4. p2 > max(p1, p3)
可以发现情况 1 和 2 结果最大只能是 max - min。而情况 3 和情况 4,以情况 3 为例,我们可以令
p2 为 1,也就是取 w2 为 min,令 p1 为 n,也就是取 w1 为 max,然后将除了 1 和 n 的所有物品
放入第 3 个包,则按照题意,p3 只会取 2,也就是取第二小的价值 min2。这种情况下结果为
max - min + min2 - min,显然一定 > max - min,情况 4 同理
因此情况 3 和 4 一定优于情况 1 和 2。接下来只考虑情况 3 和情况 4
依旧以情况 3 为例,首先想到的就是刚刚构造的方案,此时结果是 max - min + min2 - min = max + min2 - 2 * min,
显然这种情况并不一定是最优的。
这里举个反例,我们假设第三小的价值为 min3,令 min2 = min + 1,min3 = min2 + 3,此时我们将 min2
从第 3 个包中取出放入第 2 个包,此时答案应该是 max - min2 + min3 - min2 = max + min2 - 2 * min + 1,
已经优于上一个方案。
因此我们可以以 p1 = n, p2 = 1, p3 = 2 为起点,每次将第 3 个包中的最小值放入第 2 个包,令取出的三个物品
变成 p1 = n, p2 = 2, p3 = 3,然后用此时的结果更新答案,在从第 3 个包中取出最小的放入第 2 个包,直到第
3 个包中只剩一个物品,此时我们已经将所有可能的最优方案都枚举一遍了。
情况 4 和情况 3 一样,按照上述方法将所有可能最优的方案枚举一遍,全部方案中取一个最大值就是答案。
*/
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 200010;
int n;
int a[N];
int main()
{
int T;
scanf("%d", &T);
while(T--)
{
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
sort(a + 1, a + 1 + n);
int res = 0;
//情况 3
for(int i = 1; i <= n - 2; i++) res = max(res, a[n] + a[i + 1] - 2 * a[i]);
//情况 4
for(int i = n; i >= 3; i--) res = max(res, 2 * a[i] - a[1] - a[i - 1]);
printf("%d\n", res);
}
return 0;
}