顿顿总共选中了 n 块区域准备开垦田地,由于各块区域大小不一,开垦所需时间也不尽相同。据估算,其中第 i 块(1 ≤ i ≤ n)区域的开垦耗时为 ti 天。

这 n 块区域可以同时开垦,所以总耗时 tTotal 取决于耗时最长的区域,即:

tTotal = max{t1, t2, …, tn}

为了加快开垦进度,顿顿准备在部分区域投入额外资源来缩短开垦时间。

具体来说:

  • 在第 i 块区域每投入 ci 单位资源,便可将其开垦耗时缩短 1 天;
  • 耗时缩短天数以整数记,即第 i 块区域投入资源数量必须是 ci 的整数倍;
  • 在第 i 块区域最多可投入 ci × (ti - k) 单位资源,将其开垦耗时缩短为 k 天;
  • 这里的 k 表示开垦一块区域的最少天数,满足 0 < k ≤ min{t1, t2, …, tn};换言之,如果无限制地投入资源,所有区域都可以用 k 天完成开垦。

现在顿顿手中共有 m 单位资源可供使用,试计算开垦 n 块区域最少需要多少天?

输入格式

输入共 n+1 行。

输入的第一行包含空格分隔的三个正整数 n, m, k,分别表示待开垦的区域总数、顿顿手上的资源数量和每块区域的最少开垦天数。

接下来 n 行,每行包含空格分隔的两个正整数 ti 和 ci,分别表示第 i 块区域开垦耗时和将耗时缩短 1 天所需资源数量。

输出格式

输出一个整数,表示开垦 n 块区域的最少耗时。

数据范围

  • 7
  • 全部的测试数据满足:0 < n, ti, ci ≤ 10^5 且 0 < m ≤ 10^9。

输入样例1

4 9 2
6 1
5 1
6 2
7 1

输出样例1

5

样例1解释:

如下表所示,投入 5 单位资源即可将总耗时缩短至 5 天。此时顿顿手中还剩余 4 单位资源,但无论如何安排,也无法使总耗时进一步缩短。

i 基础耗时 ti 缩减 1 天所需资源 ci 投入资源数量 实际耗时
1 6 1 5 5
2 5 1 1 4
3 6 2 2 4
4 7 1 0 7

输入样例2

4 30 2
6 1
5 1
6 2
7 1

输出样例2

2

样例2解释:

投入 20 单位资源,恰好可将所有区域开垦耗时均缩短为 k=2 天;受限于 k,剩余的 10 单位资源无法使耗时进一步缩短。

题目分析

首先, 我们可能想到使用堆来解决这道题。 但是会卡在后 3 所以我们想到使用二分查找来查找最终工期,判断依据就设为当取此最终工期时需要消耗的资源量。

代码实现

堆 贪心 TLE

我们分析一下时间复杂度。 首先,在输入区域数据时, 有时间复杂度O(n log(n))。 其次,在对堆进行处理时候,有时间复杂度O(m log(m)) 所以,当 n >= m 时候,程序的时间复杂度为O(n log(n)); 当 n<= m 时,程序的时间复杂度为O(m log(m))。

#include <iostream>
#include <queue>
#include <vector>
#define x first
#define y second
using namespace std;
using PII = pair <int,int>;

int n, m, k;
priority_queue <PII, vector <PII>> heap;
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> k;
    while(n--) {
        int t, c;
        cin >> t >> c;
        heap.push({t,c});
    }
    while(heap.top().x > k && m >= heap.top().y) {
        auto t = heap.top(); heap.pop();
        t.x -= 1;
        m -= t.y;
        heap.push(t);
    }
    cout << heap.top().x;
    return 0;
} 

二分 AC

让我们分析一下时间复杂度。 首先,读入区域数据时候的循环的时间复杂度为O(n); 其次,在二分查找时,check函数的时间复杂度为O(n), 外层的二分查找为O(log(r - k))。 所以,整个程序的时间复杂度为O(n * log(r-k)) 。

#include <iostream>
#include <vector>
#define x first
#define y second
using namespace std;
using PII = pair <int,int>;
using ll = long long;

int n, m, k, l, r;
vector <PII> vec;
int check(int p) {
    int ans = 0;
    for (const auto& t : vec) {
        if (t.x <= p) continue;
        ans += (t.x - p) * t.y;
        if(ans > m) return 0x3f3f3f3f;
    }
    return ans;
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> k;
    l = k;
    while(n--) {
        int a, b;
        cin >> a >> b;
        r = max(r, a);
        vec.push_back({a,b});
    }
    while(l <= r) {
        int mid = ((r - l) >> 1) + l;
        if (check(mid) == m) {
            cout << mid;
            exit(0);
        }
        else if (check(mid) > m) l = mid + 1;
        else if (check(mid) < m) r = mid - 1;
    }
    cout << max(k,l);
    return 0;
} 

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status