机试题——新能源汽车充电桩建设策略

题目描述

随着新能源汽车的蓬勃发展，新能源汽车充电桩的覆盖密度越来越重要。某汽车公司建设充电桩的思路如下：

• 一条高速沿线，每个区域建设一个充电站，充电站内有多个充电桩，充电站之间保持合理的距离。
• 每个充电站可以覆盖相邻范围的多个区域。
• 使用n表示充电站的数目，使用station[i]数组表示第i个充电站中充电桩的数目。
• 给定一个范围r，表示每个充电站可以覆盖的相邻区域范围（|i - j| <= r，0 <= i, j <= n - 1）。
• 汽车公司打算在一些城市新增k个充电桩，如何分配这k个充电桩给充电站，使得所有区域中，被充电桩覆盖最少的区域的充电桩数目最大化。

输入描述

1. 第一行：一个整数n，表示充电站的数目（0 <= n <= 100000）。
2. 第二行：n个整数，表示每个充电站中充电桩的数目（0 <= station[i] <= 100000）。
3. 第三行：一个整数r，表示充电站可覆盖的相邻区域范围（0 <= r <= n - 1）。
4. 第四行：一个整数k，表示需要新增的充电桩数目（0 <= k <= 1000000000）。

输出描述

一个整数，表示被充电桩覆盖最少的区域的充电桩数目。

用例输入

5
1 2 4 5 0
1
2

5

最优方案是把2个充电桩都放在充电站1，这样每个充电站的充电桩数目分别为1 4 4 5 0。
区域0的覆盖充电桩为1 + 4 = 5，区域1为1 + 4 + 4 = 9，区域2为4 + 4 + 5 = 13，区域3为5 + 4 = 9，区域4为5 + 0 = 5。
充电桩覆盖数目最少是5，无法得到更优解，因此返回5。

4
4 4 4 4
0
2

4

无论怎么分配新增的3个充电桩，总有一个区域的充电桩覆盖数目是4。

解题思路

1. 问题建模：

   • 该问题可以看作是一个二分查找问题，目标是最大化所有区域中覆盖最少的充电桩数目。
   • 使用差分数组预处理每个区域的充电桩覆盖情况，然后通过二分查找确定最优的覆盖数目。

2. 差分数组预处理：

   • 使用差分数组dk来预处理每个区域的充电桩覆盖情况，减少计算复杂度。
   • 对于每个充电站i，更新差分数组dk，使得dk[i - r] += station[i]，dk[i + r + 1] -= station[i]。

3. 二分查找：

   • 使用二分查找确定最优的覆盖数目target。
   • 对于每个target，检查是否可以通过分配k个充电桩使得所有区域的覆盖数目都达到target。
   • 如果可以，则尝试更大的target；否则，尝试更小的target。

4. 贪心分配：

   • 在检查过程中，如果某个区域的覆盖数目不足target，则分配足够的充电桩，并更新差分数组。尽可能的往右边覆盖，也就是min(n, i + 2 * r+1)

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<algorithm>
#include<string>
#include<vector>
#include<unordered_map>
#include<unordered_set>
#include<queue>
#include<set>
#include<list>
#include<sstream>
#include<bitset>
#include<stack>
#include<climits>
using namespace std;

int n, r, k;

bool check(vector<long long> dk, long long target) {
    long long tk = k; // 剩余可分配的充电桩
    long long cur = 0; // 当前区域的覆盖充电桩数目
    for (int i = 0; i < n; i++) {
        cur += dk[i]; // 更新当前区域的覆盖充电桩数目
        if (cur < target) { // 如果当前区域不足target
            tk -= (target - cur); // 分配充电桩
            dk[min(n, i + 2 * r + 1)] -= (target - cur); // 更新差分数组
            cur = target; // 当前区域覆盖数目达到target
        }
    }
    return tk >= 0; // 如果分配完成，则返回true
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    vector<long long> station(n);
    for (int i = 0; i < n; i++) {
        cin >> station[i];
    }
    cin >> r >> k;

    // 差分数组预处理
    vector<long long> dk(n + 1, 0);
    for (int i = 0; i < n; i++) {
        dk[max(0, i - r)] += station[i];
        dk[min(n, i + r + 1)] -= station[i];
    }

    // 二分查找最优解
    long long l = 0, r = 2e10;
    long long res = 0;
    while (l <= r) {
        long long mid = (l + r) / 2;
        if (check(dk, mid)) {
            l = mid + 1;
            res = mid;
        } else {
            r = mid - 1;
        }
    }
    cout << res;
    return 0;
}