CSP-垦田计划-Toy模板网

这篇具有很好参考价值的文章主要介绍了CSP-垦田计划。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

问题描述

顿顿总共选中了 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 块区域的最少耗时。

解题思路：

首先强调一点：总耗时取决于耗时最长的区域。这也是我们解题的出发点，我们只需用资源把最大耗时降到最小，就等同于将最终的开垦天数降到最小。所以，我们先记录初始时的最大耗时 maxtime，然后以 maxtime 为起点，逐天降低最大耗时，当到某一天剩余资源无法再将当前最大耗时降低一天或最大耗时已降低到最少开垦天数时，循环结束。这里，我们用数组 date[i] 来记录从第 i 天再缩短一天所要的资源数。对于已经被缩短的天数，要将其所要的资源加到前一天上，例如，我们把最大耗时从7天缩短到6天，原本开垦时长为7天的区域就变为了开垦时长为6天的区域，这时候开垦时长为6天的区域就增加了，所以再降低一天所需的资源数也要增加相应的值。

100分代码：

# include <iostream>
# include <algorithm>

using namespace std;
const int maxn = 1e5 + 10;
int n, m, k;
int date[maxn];  //从i天缩短一天所要的资源数

int main()
{
	cin >> n >> m >> k;
	int t, c, maxtime = 0;
	for (int i = 1; i <= n; i++) {
		cin >> t >> c;
		//初始化从i天缩短一天所要的资源数
		date[t] += c;
		//记录目前的最大耗时
		maxtime = max(maxtime, t);
	}
	int ans = k;
	//从最大耗时开始逐次降低耗时
	//直到现有的资源无法再缩短一天或已缩短到最少开垦天数
	for (int i = maxtime; i > k; i--) {
		if (m >= date[i]) {
			//将被缩短天数所要的资源加到前一天上
			date[i - 1] += date[i];
			m -= date[i];
		}
		else {
			//现有的资源无法再缩短一天，此时的i即为最少开垦天数
			ans = i;
			break;
		}
	}
	cout << ans << endl;
	return 0;
}

以上便是我对这题的看法，很高兴与大家分享。文章来源地址https://www.toymoban.com/news/detail-459989.html

到了这里，关于CSP-垦田计划的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！