Loading... 顿顿总共选中了 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 块区域的最少耗时。 ### 数据范围 * 70% 的测试数据满足：0 < n, ti, ci ≤ 100 且 0 < m ≤ 10^6。 * 全部的测试数据满足：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 单位资源无法使耗时进一步缩短。 ### 题目分析 首先， 我们可能想到使用堆来解决这道题。 但是会卡在后 30% 的测试点。 所以我们想到使用二分查找来查找最终工期，判断依据就设为当取此最终工期时需要消耗的资源量。 ### 代码实现 #### 堆 贪心 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; } ``` 最后修改：2023 年 09 月 23 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏