支架

题目概要

有 \(n\) 根木棍，第 \(i\) 根木棍的长度是 \(a_i\)。

两根木棍可以做成一个支架。用两根长度为 \(x\) 和 \(y\) 的木棍做成的支架，上面可以摆放一件重量不超过 \(xy\) 的物品。

某人计划制作 \(m\) 个支架，然后购买 \(m\) 个重量一样的艺术品，把每个艺术品分别摆放在一个支架上。

请你告诉他购买的单个艺术品的重量最大是多少。

• \(2 \le n \le 10^6\)
• \(1 \le m \le \lfloor n/2 \rfloor\)
• \(1 \le a_i \le 10^5\)

解法

不难看出应该用最长的 \(2m\) 根木棍制作支架。问题在于如何把木棍两两配对。答案是

• 每次把最长的木棍和最短的木棍配对。

我们考虑把四根木棍配成两对的情形。设四根木棍的长度是 \(a, b, c, d\) 且 \(a \le b \le c \le d\)。把这四根木棍配成两对，有下列三种方法

• \(a, b\) 一对，\(c,d\) 一对。两个支架的承重量的最小值是 \(\min(ab, cd) = ab\)。
• \(a, c\) 一对，\(b,d\) 一对。两个支架的承重量的最小值是 \(\min(ac, bd) = ac\)。
• \(a, d\) 一对，\(b,c\) 一对。两个支架的承重量的最小值是 \(\min(ad, bc)\)。

容易验证 \(\min(ad, bc) \ge ab\) 且 \(\min(ad, bc) \ge ac\)。所以，最好的配对方法是 \(a\) 和 \(d\) 一对，\(b\) 和 \(c\) 一对。

代码

const int maxn = 1e6 + 5;
int a[maxn];

bool cmp(int x, int y) {
    return x > y;
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    sort(a, a + n, cmp); // 从大到小排序
    int l = 0, r = 2 * m - 1;
    long long ans = 1e10;
    for (int i = 0; i < m; i++) {
        ans = min(ans, (long long) a[l] * a[r]);
        l++; r--;
    }
    cout << ans << '\n';
}