LeetCode2141 同时运行 N 台电脑的最长时间

发表于 | 分类于 |
字数统计: 672 | 阅读时长 ≈ 3

链接: https://leetcode-cn.com/problems/maximum-running-time-of-n-computers/

题意

你有 n 台电脑。给你整数 n 和一个下标从 0 开始的整数数组 batteries ，其中第 i 个电池可以让一台电脑 运行 batteries[i] 分钟。你想使用这些电池让 全部 n 台电脑 同时 运行。
求可以让 n 台电脑同时运行的 最长 分钟数。

解法

二分答案

由于答案具有单调性，所以可以通过二分答案的方法来找到最大可以维持的时间
所以问题就被转化成，给定时长x，现有的电池容量是否可以维持n台电脑运行
由于需要同时供电，所以电池容量超过x的电池最长只能使用x
因此每个电池的使用时间至多为min(x, batteries[i])，所有电池的容量的和为sum
只需要满足$ n * x \leq sum $ 就一定可以满足条件
简单证明如下：对于容量超过x的m块电池，只要一直供应一台电脑就可以
对于其他容量不超过x的电池，剩余n-m台电脑没供电，只需要任意选择电池，供给余下的电脑
是一定可以维持x的时长的

郑重规定一下二分答案的写法，while(r - l > 1)，每次l和r都取mid
最后l和r会差1，l就是答案

这道题也可以贪心解，对battery进行从大到小排序
维护电池和sum值
如果电池容量大于sum / n 就让电池数减1，sum减去电池容量
知道电池容量小于等于 sum / n ，此时剩下的电池一定可以满足 维持 sum / n 时长

代码

二分答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#define ll long long
class Solution {
public:
    bool solve(int n, ll t, vector<int>& batteries) {
        ll sum = 0;
        for (ll i: batteries) {
            sum += min(i, t);
        }
        if (n * t <= sum) return true;
        return false;
    }
    long long maxRunTime(int n, vector<int>& batteries) {
        ll sum = accumulate(batteries.begin(), batteries.end(), 0L);
        ll l = 0, r = sum / n + 1;
        while(r - l > 1) {
            ll mid = l + (r - l) / 2;
            cout << l << ' ' << mid << ' ' << r << endl;
            if (solve(n, mid, batteries)) {
                ans = mid;
                l = mid;
            }
            else {
                r = mid;
            }
        }
        return ans;

    }
};

贪心

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#define ll long long
class Solution {
public:
    bool solve(int n, ll t, vector<int>& batteries) {
        ll sum = 0;
        for (ll i: batteries) {
            sum += min(i, t);
        }
        if (n * t <= sum) return true;
        return false;
    }
    long long maxRunTime(int n, vector<int>& batteries) {
        ll sum = accumulate(batteries.begin(), batteries.end(), 0L);
        sort(batteries.begin(), batteries.end(), greater<int>());
        int m = batteries.size();
        for (int i = 0; i < m; i++) {
            if (batteries[i] <= sum / n) {
                return sum / n;
            }
            sum -= batteries[i];
            n--;
        }
        return 0;

    }
};