2024.01.24-秋招-第三题-新能源汽车充电桩建设策略

TaZi SU @ 8 months ago

题目描述

在一座城市中，划分为多个区域，每个区域内建设一个充电站，充电站内设有多个充电桩，充电站之间需要保持合理的距离。定义：

n：区域充电站的数目。
station[i]：表示第 i 个充电站中充电桩的数量。
r：充电站可覆盖的相邻区域范围，满足条件 |i-j| <= r。
k：需要新增的充电桩数量。

我们的目标是合理分配这 k 个新增充电桩，使得所有区域总的被充电桩覆盖最少区域的充电桩数目最大化。

思路：二分+贪心+差分

二分每个区域被覆盖的最小充电桩数量，每个区域至少需要这么多的充电桩数量，对于给定的最低充电桩数量，判断是否可以在只分配k个充电桩的情况下实现。

贪心的做法是从左到右遍历，计算当前区域的充电桩数量，如果低于最低充电桩数量，则尽量放置充电桩在最右侧的区域，因为这样可以让右边更多的区域增加充电桩。

由于计算当前区域的充电桩数量需要累计附近的充电桩，所以每个区域的充电桩其实可以视为对一个区间的区域进行累加，在遍历过程中维护当前的充电桩数量比较简单，所以建议采用差分的方式来计算累计充电桩。

解题思路

二分法：我们采用二分搜索的方式来找到可以实现的最低覆盖充电桩数量。设定左右边界，L 为 0，R 为一个合理的最大值（如 (2 \times 10^{10})），在这个范围内寻找最小的充电桩覆盖数量。
覆盖量计算：使用差分数组（或前缀和）来快速计算每个区域在覆盖范围内的充电桩数量。通过维护一个差分数组 d 来简化范围累加的计算。
贪心分配充电桩：在判断某个覆盖数量 x 是否可以实现时，优先从右侧区域向左分配充电桩。若当前区域的充电桩数量低于 x，则尽量在右侧的区域放置充电桩，尽可能使更多的区域得到覆盖。

算法步骤

初始化输入，包括区域数量 n、充电桩数量 a、覆盖范围 r 和需要新增的充电桩数量 k。
利用差分数组计算每个区域的实际覆盖充电桩数量。
实现一个函数 check，用于判断在给定的最低充电桩数量 x 下，是否能够通过分配最多 k 个充电桩实现该覆盖。
使用二分搜索来找到最大的 L，即最大的最低充电桩覆盖数量。

JavaScript

// 检查在新增k个充电桩的情况下是否可以实现至少x个覆盖数量
function check(d, r, x, n, k) {
    let td = new Array(n + 1).fill(0); // 用于记录每个区域需要新增的充电桩数量
    let cur = 0; // 当前新增的充电桩数量

    // 遍历区域，从r开始，计算需要新增的充电桩数量
    for (let i = r; i < n; i++) {
        // 如果当前索引超出覆盖范围，减去相应的新增充电桩
        if (i > 2 * r) {
            cur -= td[i - 2 * r - 1];
        }
        // 如果当前区域的充电桩数量不足x，则需要新增充电桩
        if (d[i - r] + cur < x) {
            td[i] = x - d[i - r] - cur; // 计算需要新增的充电桩数量
            cur += td[i]; // 更新当前的新增充电桩数量
        }
    }

    // 存储实际覆盖的充电桩数量
    let b = new Array(n + 1).fill(0);
    
    // 更新覆盖数组b，计算每个区域的充电桩数量
    for (let i = 0; i < n; i++) {
        b[Math.max(i - r, 0)] += td[i]; // 更新覆盖范围
        b[Math.min(n, i + r + 1)] -= td[i]; // 超出范围的部分减去
    }
    
    // 计算每个区域的实际覆盖数量
    for (let i = 1; i < n; i++) {
        b[i] += b[i - 1]; // 前缀和
    }
    
    let need = 0; // 记录最终需要的充电桩数量
    // 在最后几个区域检查所需的充电桩数量
    for (let i = n - r; i < n; i++) {
        need = Math.max(need, x - b[i] - d[i]); // 计算需要增加的充电桩数量
    }
    
    // 更新最后需要的充电桩数量
    b[Math.max(0, n - r - 1)] += need;
    
    // 计算所有新增充电桩的总和
    let sum = td.reduce((acc, val) => acc + val, 0);
    
    // 判断总新增的充电桩是否小于等于k
    return sum <= k;
}

// 使用readline模块从标准输入读取数据
let readline = require('readline');
let rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

// 提示用户输入区域数量n
rl.question("Enter n: ", function(n) {
    n = parseInt(n); // 转换为整数
    // 提示用户输入充电桩数量数组
    rl.question("Enter array a: ", function(aStr) {
        let a = aStr.split(' ').map(Number); // 将输入的字符串转换为数字数组
        // 提示用户输入覆盖范围r
        rl.question("Enter r: ", function(r) {
            r = parseInt(r); // 转换为整数
            // 提示用户输入需要新增的充电桩数量k
            rl.question("Enter k: ", function(k) {
                k = parseInt(k); // 转换为整数
                
                // 初始化差分数组d
                let d = new Array(n + 1).fill(0);
                
                // 构造差分数组d
                for (let i = 0; i < n; i++) {
                    d[Math.max(i - r, 0)] += a[i]; // 当前区域的充电桩数加到最左侧的覆盖区域
                    d[Math.min(n, i + r + 1)] -= a[i]; // 超出覆盖范围的部分减去
                }
                
                // 计算每个区域的实际充电桩数量
                for (let i = 1; i < n; i++) {
                    d[i] += d[i - 1]; // 前缀和
                }
                
                let L = 0; // 二分搜索的下界
                let R = 2e10; // 二分搜索的上界

                // 二分搜索查找最大的最低覆盖充电桩数量
                while (L < R) {
                    let mid = (L + R + 1) >> 1; // 计算中间值
                    // 调用check函数判断是否可以在k个充电桩内实现至少mid个覆盖数量
                    if (check(d, r, mid, n, k)) {
                        L = mid; // 如果可以实现，则更新下界
                    } else {
                        R = mid - 1; // 否则更新上界
                    }
                }
                // 输出最大的最低覆盖充电桩数量
                console.log(L);
                rl.close(); // 关闭readline接口
            });
        });
    });
});

Java

import java.util.Scanner;

public class ChargingStations {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取区域数量
        long n = scanner.nextLong();
        long[] a = new long[(int) n]; // 存储每个充电站的充电桩数量
        
        // 读取每个充电站中的充电桩数量
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextLong();
        }
        
        // 读取覆盖范围和新增充电桩数量
        long r = scanner.nextLong();
        long k = scanner.nextLong();
        
        // 差分数组，长度为n+1
        long[] d = new long[(int) (n + 1)];
        
        // 构造差分数组d
        for (int i = 0; i < n; i++) {
            d[(int) Math.max(i - r, 0)] += a[i]; // 当前区域的充电桩数加到最左侧的覆盖区域
            d[(int) Math.min(n, i + r + 1)] -= a[i]; // 超出覆盖范围的部分减去
        }
        
        // 计算每个区域的实际充电桩数量
        for (int i = 1; i < n; i++) {
            d[i] += d[i - 1]; // 前缀和
        }
        
        long L = 0; // 二分搜索的下界
        long R = (long) 2e10; // 二分搜索的上界
        
        // 二分搜索查找最大的最低覆盖充电桩数量
        while (L < R) {
            long mid = (L + R + 1) >> 1; // 计算中间值
            // 调用check函数判断是否可以在k个充电桩内实现至少mid个覆盖数量
            if (check(d, r, mid, n, k)) {
                L = mid; // 如果可以实现，则更新下界
            } else {
                R = mid - 1; // 否则更新上界
            }
        }
        
        // 输出最大的最低覆盖充电桩数量
        System.out.println(L);
    }

    // 检查是否可以在新增k个充电桩的情况下使得覆盖数量至少为x
    private static boolean check(long[] d, long r, long x, long n, long k) {
        long[] td = new long[(int) (n + 1)]; // 用于记录需要新增的充电桩数量
        long cur = 0; // 当前新增的充电桩数量
        
        // 遍历区域，从r开始，计算需要新增的充电桩数量
        for (long i = r; i < n; i++) {
            // 如果当前索引超出覆盖范围，减去相应的新增充电桩
            if (i > 2 * r) {
                cur -= td[(int) (i - 2 * r - 1)];
            }
            // 如果当前区域的充电桩数量不足x，则需要新增充电桩
            if (d[(int) (i - r)] + cur < x) {
                td[(int) i] = x - d[(int) (i - r)] - cur; // 计算需要新增的充电桩数量
                cur += td[(int) i]; // 更新当前的新增充电桩数量
            }
        }
        
        // 存储实际覆盖的充电桩数量
        long[] b = new long[(int) (n + 1)];
        
        // 更新覆盖数组b，计算每个区域的充电桩数量
        for (int i = 0; i < n; i++) {
            b[(int) Math.max(i - r, 0)] += td[i]; // 更新覆盖范围
            b[(int) Math.min(n, i + r + 1)] -= td[i]; // 超出范围的部分减去
        }
        
        // 计算每个区域的实际覆盖数量
        for (int i = 1; i < n; i++) {
            b[i] += b[i - 1]; // 前缀和
        }
        
        long need = 0; // 记录最终需要的充电桩数量
        // 在最后几个区域检查所需的充电桩数量
        for (long i = n - r; i < n; i++) {
            need = Math.max(need, x - b[(int) i] - d[(int) i]); // 计算需要增加的充电桩数量
        }
        
        // 更新最后需要的充电桩数量
        b[(int) Math.max(0, n - r - 1)] += need;
        long sum = 0; // 计算新增充电桩的总数
        
        // 计算所有新增充电桩的总和
        for (long value : td) {
            sum += value;
        }
        
        // 判断总新增的充电桩是否小于等于k
        return sum <= k;
    }
}

Python

n = int(input())
a = list(map(int, input().split()))
r = int(input())
k = int(input())
d = [0] * (n + 1)
for i, v in enumerate(a):
	# 差分
    d[max(i - r, 0)] += v
    d[min(n, i + r + 1)] -= v
for i in range(1, n):
    d[i] += d[i - 1]
L, R = 0, int(2e10)


def check(x):
    td, cur = [0] * (n + 1), 0
    b = [0] * (n + 1)
    # 用cur维护当前附近范围增加的累计充电桩数量
    for i in range(r, n):
        if i > 2 * r:
        	# 超过2 * r的范围则需要减去
            cur -= td[i - 2 * r - 1]
        if d[i - r] + cur < x:
            td[i] = x - d[i - r] - cur
            cur += td[i]
    for i, v in enumerate(td):
        b[max(i - r, 0)] += v
        b[min(n, i + r + 1)] -= v
    for i in range(1, n):
        b[i] += b[i - 1]
    need = 0
    for i in range(n - r, n):
        need = max(need, x - b[i] - d[i])
    td[max(0, n - r - 1)] += need
    return sum(td) <= k

while L < R:
    mid = L + R + 1 >> 1
    if check(mid):
        L = mid
    else:
        R = mid - 1
print(L)

C++

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;

void solve() {
    int n, k, r;
    cin >> n; // 输入区域数量
    vector<int> a(n);
    vector<LL> d(n + 1, 0); // 差分数组初始化

    // 输入每个充电站的充电桩数量
    for (int i = 0; i < n; ++i) 
        cin >> a[i];

    cin >> r >> k; // 输入覆盖范围和需要新增的充电桩数量

    // 计算差分数组
    for (int i = 0; i < n; ++i) {
        d[max(i - r, 0)] += a[i]; // 当前区域的充电桩数量加到其覆盖的最左侧区域
        d[min(n, i + r + 1)] -= a[i]; // 超出覆盖范围的部分减去
    }

    // 计算每个区域的实际充电桩数量
    for (int i = 1; i < n; ++i) {
        d[i] += d[i - 1]; // 前缀和累加
    }

    LL L = 0, R = (LL)2e10; // 设置二分搜索的边界

    // 判断是否可以实现的函数
    function<bool(LL)> check = [&](LL x) -> bool {
        vector<LL> td(n + 1, 0), b(n + 1, 0); // 新增充电桩数组和实际覆盖数组
        LL cur = 0; // 当前增加的充电桩数量
        
        for (int i = r; i < n; ++i) {
            if (i > 2 * r) {
                cur -= td[i - 2 * r - 1]; // 维护当前的充电桩数量
            }
            // 如果当前区域充电桩不足，则需要添加
            if (d[i - r] + cur < x) {
                td[i] = x - (d[i - r] + cur); // 计算需要新增的充电桩
                cur += td[i]; // 更新当前新增充电桩数量
            }
        }

        // 更新覆盖数组
        for (int i = 0; i < n; ++i) {
            b[max(i - r, 0)] += td[i]; // 更新覆盖范围
            b[min(n, i + r + 1)] -= td[i]; // 超出范围的部分减去
        }
        
        // 计算实际覆盖
        for (int i = 1; i < n; ++i) 
            b[i] += b[i - 1]; 

        LL need = 0; // 记录最终需要的充电桩数量
        for (int i = n - r; i < n; ++i) {
            need = max(need, x - b[i] - d[i]); // 计算在最后几区域所需的充电桩
        }

        td[max(0, n - r - 1)] += need; // 更新最后需要添加的充电桩
        LL res = 0;
        for (LL v : td) {
            res += v; // 计算新增充电桩的总数
        }
        return res <= k; // 判断是否在k范围内
    };

    // 二分搜索找到最大的L
    while (L < R) {
        LL mid = L + R + 1 >> 1; // 计算中间值
        if (check(mid)) {
            L = mid; // 如果可以实现，则更新L
        } else {
            R = mid - 1; // 否则更新R
        }
    }

    cout << L << endl; // 输出结果
}

signed main() {
    solve(); // 执行solve函数
    return 0; // 返回0
}

ID

Time

1000ms

Memory

256MiB

Difficulty

Tags

# Submissions

113

Accepted

Uploaded By

TaZi

1 solutions

题目描述

思路：二分+贪心+差分

解题思路

算法步骤

JavaScript

Java

Python

C++

Information

Status

Development

Support