CCF-CSP真题《202303-2 垦田计划》思路+python，c++满分题解
想查看其他题的真题及题解的同学可以前往查看：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 全部的测试数据满足：0 |
真题来源：矩阵运算
感兴趣的同学可以如此编码进去进行练习提交
思路讲解：
这道题也不难，使用标志数组记录耗时为i天的区域降低一天的总花费，然后从高向低降，最后就可以得出答案了。
c++满分题解：
#include#includeusing namespace std;int n, k;long long int m;maptim, 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;} 运行结果：
来源地址：https://blog.csdn.net/weixin_53919192/article/details/131490410
免责声明：
① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的，并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据，供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。
② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
