1934(div2)

A. Too Min Too Max

在数组中选择 4 个下标求表达式的最大值：

| a_{i} - a_{j} | + | a_{j} - a_{k} | + | a_{k} - a_{l} | + | a_{l} - a_{i} |

其中， $i$ 、 $j$ 、 $k$ 、 $l$ 是数组 $a$ 的四个不同的索引，其中 $1 \leq i, j, k, l \leq n$ 。

void solve() {
    int n;cin >> n;vector<int> a(n);for (auto& i : a)cin >> i;
    sort(a.begin(), a.end());
    cout << abs(a[n - 1] - a[0]) + abs(a[0] - a[n - 2]) + abs(a[n - 2] - a[1]) + abs(a[1] - a[n - 1]) << '\n';
}

B. Yet Another Coin Problem

要求用 1，3，6，10，15 这 5 种硬币凑成 $n$ ，求使用的最少的硬币数。

题目所给的数据范围较大 ( $1 \leq n \leq 10^{9}$ )所以直接开 1e9 的数组肯定是不行的，但是由于 10 和 15 其实差距挺大的，对于较大的数据，15 一定是使用的最多的，所以，可以稍微分治一下，当很大时，就先除以 15 直到没那么大为止。

vector<int> coins = {1, 3, 6, 10, 15};
vector<int> dp(1e7 + 1, INT_MAX);
void solve() {
    int n; cin >> n;
    int x = 0;
    if (n >= 1e5) {
        x = (n - 1e5) / 15;
        n -= x * 15;
    }
    cout << x + dp[n] << '\n';
}
int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    dp[0] = 0;
    for (int i = 1; i <= 1e7; i++) {
        for (int coin : coins) {
            if (i - coin >= 0) {
                dp[i] = min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    int _ = 1;
    cin >> _;
    while (_--)
        solve();
}

C. Find a Mine

交互题

(待更 $\dots$ )
鉴于这几题都是交互和构造相关，对我现在水平提升有限，所以暂时不补。