CFf1659C Line Empire

题目大意

在一条坐标轴上有\(n\)个点需要占领，每个节点在\(x_i\)，初始节点在\(0\)处，且基地也在\(0\)处 每次行动时，设当前基地在\(p\)处,那么可以做以下行动: * 把基地移动到一个已经占领的点\(x_i\)，耗费\(a * |x_i - p|\) * 占领一个没有被占领的节点，消耗\(b * |x_i - p|\)

给定\(a,b,x_i(1\le n \le 2*10^5, 1 \le a, b \le 10^5)\),求占领所有节点的耗费最小值。

题目链接 ## 思路 我们来考虑占领的最终状况。

我们把基地定在了\(x_p\)处，然后把所有点给占领了。 我们设\(sum1\)是点的距离的前缀和。 那么占领\(x_p\)之后的所有点的费用就是\((sum1[n] - sum1[i] - (n - i) * x[i]) * b\) 那么前面的点呢？ 我们发现，不管我们什么时候移动基地，移动基地的费用都是\(a * x_p\) 所以我们最有解法一定是占领一个点，那么就把基地移动过去。这样我们占领的费用就是\(b * 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;
}

• 本文作者： 水蓝络合物
• 本文链接： https://miku39393939.github.io/2022/05/13/cf1659C/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！