【Codeforces】1659C Line Empire 题解

题目大意

在一条坐标轴上有 $n$ 个点需要占领，每个节点在 $x_i$，初始节点在 $0$ 处，且基地也在 $0$ 处。每次行动时，设当前基地在 $p$ 处，那么可以做以下行动：

• 把基地移动到一个已经占领的点 $x_i$，耗费 $a \cdot |x_i - p|$
• 占领一个没有被占领的节点，消耗 $b \cdot |x_i - p|$

给定 $a, b, x_i\ (1 \le n \le 2 \cdot 10^5,\ 1 \le a, b \le 10^5)$。

题目链接

思路

我们来考虑占领的最终状况。

我们把基地定在了 $x_p$ 处，然后把所有点给占领了。设 $sum1$ 是点的距离的前缀和，那么在基地 $x_p$ 后面所有点的占领费用为 $(sum1[n] - sum1[i] - (n-i) \cdot x[i]) \cdot b$。

那么前面的点呢？我们发现，不管我们什么时候移动基地，移动基地的费用都是 $a \cdot x_p$。所以最优解法一定是占领一个点后立即把基地移动过去，这样前面所有点的占领费用就是 $b \cdot x_p$。

可以发现，指定最终基地的落脚点，可以 $O(1)$ 地算出费用，那么我们就枚举基地的落脚点，然后更新答案。

代码

#include <cstdio>
#include <iostream>
using namespace std;

const int maxN = 2e5 + 7;
int T, n;
long long a, b, x[maxN], sum1[maxN];

int main()
{
    scanf("%d", &T);
    while(T--) {
        scanf("%d%lld%lld", &n, &a, &b);
        for(int i = 1; i <= n; ++i) {
            scanf("%lld", &x[i]);
            sum1[i] = sum1[i - 1] + x[i];
        }
        long long ans = 1LL << 62;
        for(int i = 0; i <= n; ++i) {
            long long forward = x[i] * b, after = (sum1[n] - sum1[i] - (n - i) * x[i]) * b;
            ans = min(ans, forward + after + a * x[i]);
        }
        printf("%lld\n", ans);
    }
    return 0;
}