Epifi

01Request Redirection

The hackers of Hackerland want to deploy their applications on n servers. The ith server has requests[i] requests to serve but can serve a maximum of max_req[i] requests only. In order to balance the load, the hackers need to redirect some requests of ith server to some other server. For each request that is redirecting the request from ith server to jth server, the latency is |i-j| where |i-j| represents the absolute value of i-j. The max_latency is defined as the maximum latency induced among all the redirections. Given the number of servers n, requests array, find the minimum possible max_latency if the requests are redirected properly. Note that each server has to serve less than the maximum requests it can serve. If there is no way to serve all the requests, report -1 as the answer. Function Description Complete the function getMinLatency in the editor. getMinLatency has the following parameters:

requests[n]: An array of integers
max_req[n]: An array of integers Returns int: The minimal max_latency possible respecting the given conditions.

Constraints

1 ≤ n ≤ 10⁵

解法

二分答案 + 贪心检验。先看是否 sum(max_req) ≥ sum(requests)，否则返回 -1。对延迟 L 二分：在 L 内能否完成重分配？用双指针/贪心扫一遍：从左到右维护"溢出"在窗口 L 内推给后续可吸收的位置即可。时间复杂度 O(n log n)，空间复杂度 O(n)。

from typing import List

def getMinLatency(requests: List[int], max_req: List[int]) -> int:
    n = len(requests)
    if sum(requests) > sum(max_req):
        return -1

    def feasible(L: int) -> bool:
        diff = [requests[i] - max_req[i] for i in range(n)]
        for i in range(n):
            if diff[i] <= 0:
                continue
            need = diff[i]
            for j in range(max(0, i - L), min(n, i + L + 1)):
                if j == i or diff[j] >= 0:
                    continue
                take = min(need, -diff[j])
                diff[j] += take
                need -= take
                if need == 0:
                    break
            if need > 0:
                return False
        return True

    lo, hi = 0, n
    while lo < hi:
        mid = (lo + hi) // 2
        if feasible(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

class Solution {
    int getMinLatency(int[] requests, int[] max_req) {
        int n = requests.length;
        long sumR = 0, sumM = 0;
        for (int x : requests) sumR += x;
        for (int x : max_req) sumM += x;
        if (sumR > sumM) return -1;
        int lo = 0, hi = n;
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (feasible(requests, max_req, mid)) hi = mid;
            else lo = mid + 1;
        }
        return lo;
    }

    private boolean feasible(int[] req, int[] mx, int L) {
        int n = req.length;
        long[] diff = new long[n];
        for (int i = 0; i < n; i++) diff[i] = (long) req[i] - mx[i];
        for (int i = 0; i < n; i++) {
            if (diff[i] <= 0) continue;
            long need = diff[i];
            for (int j = Math.max(0, i - L); j < Math.min(n, i + L + 1) && need > 0; j++) {
                if (j == i || diff[j] >= 0) continue;
                long take = Math.min(need, -diff[j]);
                diff[j] += take;
                need -= take;
            }
            if (need > 0) return false;
        }
        return true;
    }
}

class Solution {
public:
    int getMinLatency(vector<int>& requests, vector<int>& max_req) {
        int n = requests.size();
        long long sumR = 0, sumM = 0;
        for (int x : requests) sumR += x;
        for (int x : max_req) sumM += x;
        if (sumR > sumM) return -1;
        int lo = 0, hi = n;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (feasible(requests, max_req, mid)) hi = mid;
            else lo = mid + 1;
        }
        return lo;
    }

private:
    bool feasible(vector<int>& req, vector<int>& mx, int L) {
        int n = req.size();
        vector<long long> diff(n);
        for (int i = 0; i < n; i++) diff[i] = (long long) req[i] - mx[i];
        for (int i = 0; i < n; i++) {
            if (diff[i] <= 0) continue;
            long long need = diff[i];
            for (int j = max(0, i - L); j < min(n, i + L + 1) && need > 0; j++) {
                if (j == i || diff[j] >= 0) continue;
                long long take = min(need, -diff[j]);
                diff[j] += take;
                need -= take;
            }
            if (need > 0) return false;
        }
        return true;
    }
};