想查看其他题的真题及题解的同学可以前往查看：CCF-CSP真题附题解大全
| 试题编号： | 202303-2 | |||||||||||||||||||||||||
| 试题名称： | 垦田计划 | |||||||||||||||||||||||||
| 时间限制： | 1.0s | |||||||||||||||||||||||||
| 内存限制： | 512.0MB | |||||||||||||||||||||||||
| 问题描述： |
问题描述顿顿总共选中了 n 块区域准备开垦田地，由于各块区域大小不一，开垦所需时间也不尽相同。据估算，其中第 i 块（1≤i≤n）区域的开垦耗时为 ti 天。这 n 块区域可以同时开垦，所以总耗时 tTotal 取决于耗时最长的区域，即：tTotal=max{t1,t2,⋯,tn} 为了加快开垦进度，顿顿准备在部分区域投入额外资源来缩短开垦时间。具体来说：
现在顿顿手中共有 m 单位资源可供使用，试计算开垦 n 块区域最少需要多少天？ 输入格式从标准输入读入数据。 输入共 n+1 行。 输入的第一行包含空格分隔的三个正整数 n、m 和 k，分别表示待开垦的区域总数、顿顿手上的资源数量和每块区域的最少开垦天数。 接下来 n 行，每行包含空格分隔的两个正整数 ti 和 ci，分别表示第 i 块区域开垦耗时和将耗时缩短 1 天所需资源数量。 输出格式输出到标准输出。 输出一个整数，表示开垦 n 块区域的最少耗时。 样例输入1
样例输出1
样例解释如下表所示，投入 5 单位资源即可将总耗时缩短至 5 天。此时顿顿手中还剩余 4 单位资源，但无论如何安排，也无法使总耗时进一步缩短。
样例输入2
样例输出2
样例解释投入 20 单位资源，恰好可将所有区域开垦耗时均缩短为 k=2 天；受限于 k，剩余的 10 单位资源无法使耗时进一步缩短。 子任务70% 的测试数据满足：0<n,ti,ci≤100 且 0<m≤106； 全部的测试数据满足：0<n,ti,ci≤105 且 0<m≤109。 |
真题来源：矩阵运算
感兴趣的同学可以如此编码进去进行练习提交
思路讲解：
这道题也不难，使用标志数组记录耗时为i天的区域降低一天的总花费，然后从高向低降，最后就可以得出答案了。
c++满分题解：
#include<bits/stdc++.h>
#include<iostream>
using namespace std;
int n, k;
long long int m;
map<int, int>tim, res, flag;
int main(){
cin >> n >> m >> k;
int max = 0;
for(int i = 0; i < n; ++i){
cin >> tim[i] >> res[i];
max = max > tim[i] ? max : tim[i];
flag[tim[i]] += res[i];
// flag[i]为用时i天的区域缩短一天所用时
}
for(int i = max; i > 0; i--){
//cout << i << " " << flag[i] << endl;
if(max == k)break;
if(m > flag[i]){
m = m - flag[i];
flag[i - 1] += flag[i];
max--;
}else break;
}
cout << max;
return 0;
}
运行结果：
文章出处登录后可见！
