第29次CCF计算机软件能力认证-2-垦田计划
垦田计划
刷新
时间限制： 1.0 秒
空间限制： 512 MiB
下载题目目录（样例文件）
题目描述
顿顿总共选中了 nn 块区域准备开垦田地，由于各块区域大小不一，开垦所需时间也不尽相同。据估算，其中第 ii 块（1≤i≤n1≤i≤n）区域的开垦耗时为 titi 天。这 nn 块区域可以同时开垦，所以总耗时 tTotaltTotal 取决于耗时最长的区域，即：tTotal=max{t1,t2,⋯,tn}tTotal=max{t1,t2,⋯,tn}
为了加快开垦进度，顿顿准备在部分区域投入额外资源来缩短开垦时间。具体来说：
-
在第 ii 块区域每投入 cici 单位资源，便可将其开垦耗时缩短 11 天；
-
耗时缩短天数以整数记，即第 ii 块区域投入资源数量必须是 cici 的整数倍；
-
在第 ii 块区域最多可投入 ci×(ti−k)ci×(ti−k) 单位资源，将其开垦耗时缩短为 kk 天；
-
这里的 kk 表示开垦一块区域的最少天数，满足 0<k≤min{t1,t2,⋯,tn}0<k≤min{t1,t2,⋯,tn}；换言之，如果无限制地投入资源，所有区域都可以用 kk 天完成开垦。
现在顿顿手中共有 mm 单位资源可供使用，试计算开垦 nn 块区域最少需要多少天？
输入格式
从标准输入读入数据。
输入共 n+1n+1 行。
输入的第一行包含空格分隔的三个正整数 nn、mm 和 kk，分别表示待开垦的区域总数、顿顿手上的资源数量和每块区域的最少开垦天数。
接下来 nn 行，每行包含空格分隔的两个正整数 titi 和 cici，分别表示第 ii 块区域开垦耗时和将耗时缩短 11 天所需资源数量。
输出格式
输出到标准输出。
输出一个整数，表示开垦 nn 块区域的最少耗时。
样例1输入
4 9 2
6 1
5 1
6 2
7 1
样例1输出
5
样例1解释
如下表所示，投入 55 单位资源即可将总耗时缩短至 55 天。此时顿顿手中还剩余 44 单位资源，但无论如何安排，也无法使总耗时进一步缩短。
| ii | 基础耗时 titi | 缩减 11 天所需资源 cici | 投入资源数量 | 实际耗时 |
|---|---|---|---|---|
| 1 | 6 | 1 | 1 | 5 |
| 2 | 5 | 0 | ||
| 3 | 6 | 2 | 2 | |
| 4 | 7 | 1 |
样例2输入
4 30 2
6 1
5 1
6 2
7 1
样例2输出
2
样例2解释
投入 2020 单位资源，恰好可将所有区域开垦耗时均缩短为 k=2k=2 天；受限于 kk，剩余的 1010 单位资源无法使耗时进一步缩短。
子任务
70%70% 的测试数据满足：0<n,ti,ci≤1000<n,ti,ci≤100 且 0<m≤1e6 0<m≤1e6；
全部的测试数据满足：0<n,ti,ci≤1e5 0<n,ti,ci≤1e5 且 0<m≤1e9 0<m≤1e9。
70分代码，拿了就走
用最大的天数dmax作为循环变量，每次循环开始时-1
计算n块田地总天数-1需要的资源
判断m和资源的大小
如果m>tmp，则m=m-tmp
否则说明-1行不通了，最少的天数就是dmax+1
这里还用了一个小优化，就是当天数来到dmin的时候，再想-1的话就是每块田都要-1，直接判断每块田-1所需要的资源数和与m的大小，虽然用处不大
#include <iostream>
using namespace std;
int ti[100010], ci[100010];int main()
{int n, m, k;cin >> n >> m >> k;int dmax = 0;int dmin = 0;int dec_sum = 0;for (int i = 1; i <= n; i++){cin >> ti[i] >> ci[i];dmax = max(dmax, ti[i]);dmin = min(dmin, ti[i]);dec_sum += ci[i];}while (dmax > k){int tmp = 0;dmax--;if (dmax > dmin){for (int i = 1; i <= n; i++){if (ti[i] > dmax)tmp += ci[i];}}else{tmp = dec_sum;}if (tmp <= m){m -= tmp;}else{dmax++;break;}}cout << dmax << endl;
}
100分代码 追求极致
前面循环是dmax每次-1
这里我们想到让dmax每次-100，因为-10还是超时
关键的地方就是如何计算-100的情况下每块田所需的资源
假如有三块田 ，所需天数分别为550 , 500 , 450
那么dmax=550，，先-100之后dmax=450 > dmin(=100)
遍历田地数组
第一块田450 = dmax，跳过
第二块田500 > dmax，
t1[i] > dmax
ti[i]天数降低到dmax所需的资源就是 ci[i] * (ti[i] - dmax)
第三块田550>dmax
t2[i] 减到多少天合适呢
dmax = 450 , ti[2] = 550
减到和dmax一样大需要的资源：ci[i] * (ti[i] - dmax)
用ai[i] 数组保存下每块田减少的天数，用于后面的精细查询还原ti[i]数组的状态
精细查询就和上面的一样，dmax每次-1，直到找到正确答案即可
#include <iostream>
using namespace std;
int ti[100010], ci[100010], ai[100010];
/*
4 30 2
6 1
5 1
6 2
7 12
*/int main()
{int n, m, k;cin >> n >> m >> k;int dmax = 0, dmin = 0, dec_sum = 0;for (int i = 1; i <= n; i++){cin >> ti[i] >> ci[i];dmax = max(dmax, ti[i]);dmin = min(dmin, ti[i]);dec_sum += ci[i];}while (dmax > k){int tmp = 0;dmax -= 100;if (dmax > dmin){for (int i = 1; i <= n; i++){if (ti[i] > dmax){ai[i] = ti[i] - dmax;tmp += ci[i] * ai[i];ti[i] -= ai[i];}}}elsetmp = dec_sum * 100;if (tmp <= m)m -= tmp;else{dmax += 100;int num = 100;for (int i = 1; i <= n; i++){ti[i] += ai[i];}while (dmax > k && num--){int tmp0 = 0;dmax--;if (dmax > dmin){for (int i = 1; i <= n; i++){if (ti[i] > dmax)tmp0 += ci[i];}}else{tmp0 = dec_sum;}if (tmp0 <= m){m -= tmp0;}else{dmax++;break;}}break;}}cout << dmax << endl;
}