HKU 2023 Practice Contest D Bricks and Bags

题目来自 Codeforces Round #831 (Div.1 + Div.2) T3。link

  This article provides a feasible solution to a certain competitive programming problem.   If you have better solutions, feel free to share with me!

Problem Description

\(n\) bricks numbered from \(1\) to \(n\). Brick \(i\) has a weight of \(a_i\).

A has \(3\) bags numbered from \(1\) to \(3\). For each brick, A must put it into one of the bags. After this, each bag must contain at least one brick.

B will take exactly one brick from each bag, \(w_j\) is the weight of brick B takes from bag \(j\). The score is calculated as \(|w_1-w_2|+|w_2-w_3|\).

B will take the bricks in such a way that minimises the score. What is the maximum possible final score if A distributes the bricks optimally?

Tutorial

对所有砖块按照权值从小到大排序：此时 \(a_1\) 为最小值，\(a_n\) 为最大值。

很容易想到一种贪心做法：

• \(B_1=\{a_2,...a_{n-1}\}, B_2={a_1}, B_3={a_n}\) 或
• \(B_1=\{a_2,...a_{n-1}\}, B_2={a_n}, B_3={a_1}\)

那么最后的答案为 \((a_n-a_1)+\max(a_2-a_1, a_n-a_{n-1})\)。满心欢喜的交上去，结果 WA 了。

下面是一个 counter case：\(\{1, 2, 99, 100\}\)。按照上述贪心算法得到的分数是 \(100\)。然而，如果这样进行分配我们能够得到 \(195\) 的高额分数：\(\{99\}, \{1, 2\}, \{100\}\)。观察这两种分法：

• \(\{99,2\}, \{1\}, \{100\}=100\).
• \(\{99\}, \{2, 1\}, \{100\}=195\).

可以发现，在第一种分法中，\(2\) 的存在使得明显更有价值的 \(99\) 无法被利用。这启发我们我们不断尝试将 \(B_1\) 中的数挪到 \(B_2\)，如果这样做产生的收益大于付出的代价，我们更新对应的分数。

举例来说：将 \(2\) 挪到中间，我们获得的收益是 \(99-2=97\)。付出的代价是 \(2\times (2-1)=2\)；收益大于代价，我们更新答案为 \(100+97-2=195\)。

最大值放在 \(B_2\) 中时的情况类似；唯一的区别是我们从后往前枚举断点。

Code Implementation

#include <iostream>
#include <algorithm>
#include <cmath>
 
using namespace std;
 
const int MAX_N = 2e5 + 10;
 
long long a[MAX_N];
 
int main() {
 
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        for (int i = 1; i <= n; ++i)
            cin >> a[i];
        sort(a + 1, a + n + 1);
        long long ans = a[n] - a[1] + a[2] - a[1];
        for (int i = 2; i < n; ++i)
            ans = max(ans, a[n] - a[i] + a[i + 1] - a[i]);
        ans = max(ans, a[n] - a[1] + a[n] - a[n - 1]);
        for (int i = n - 1; i > 1; --i)
            ans = max(ans, a[i] - a[1] + a[i] - a[i - 1]);
        cout << ans << endl;
    }
 
    return 0;
}