CCF-CSP 202303-2 垦田计划
😸题目要求
🐈⬛问题描述
顿顿总共选中了 n n n 块区域准备开垦田地,由于各块区域大小不一,开垦所需时间也不尽相同。据估算,其中第 i i i 块 ( 1 ≤ i ≤ n ) (1 \leq i \leq n) (1≤i≤n) 区域的开垦耗时为 t i t_i ti 天。这 n n n 块区域可以同时开垦,所以总耗时 t T o t a l t_{Total} tTotal 取决于耗时最长的区域,即:
t T o t a l = m a x { t 1 , t 2 , ⋅ ⋅ ⋅ , t n } \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad t_{Total}=max\{t_1,t_2,···,t_n\} tTotal=max{ t1,t2,⋅⋅⋅,tn}
为了加快开垦进度,顿顿准备在部分区域投入额外资源来缩短开垦时间。具体来说:
- 在第 i i i 块区域每投入 c i c_i ci 单位资源,便可将其开垦耗时缩短 1 1 1 天;
- 耗时缩短天数以整数记,即第 i i i 块区域投入资源数量必须是 c i c_i ci 的整数倍;
- 在第 i i i 块区域最多可投入 c i × ( t i − k ) c_i×(t_i-k) ci×(ti−k) 单位资源,将其开垦耗时缩短为 k k k 天;
- 这里的 k k k 表示开垦一块区域的最少天数,满足 0 < k ≤ m i n { t 1 , t 2 , ⋅ ⋅ ⋅ , t n } 0 < k \leq min\{t_1,t_2,···,t_n\} 0<k≤min{ t1,t2,⋅⋅⋅,tn};换言之,如果无限制地投入资源,所有区域都可以用 k k k 天完成开垦。
现在顿顿手中共有 m m m单位资源可供使用,试计算开垦 n n n 块区域最少需要多少天?
🐈⬛输入格式
从标准输入读入数据。
输入共 n + 1 n+1 n+1 行。
输入的第一行包含空格分隔的三个正整数 n n n、 m m m 和 k k k,分别表示待开垦的区域总数、顿顿手上的资源数量和每块区域的最少开垦天数。
🐈⬛输出格式
输出到标准输出。
输出一个整数,表示开垦 n n n 块区域的最少耗时。
🐈⬛样例输入1
4 9 2
6 1
5 1
6 2
7 1
🐈⬛样例输出1
5
🐈⬛样例解释1
如下表所示,投入 5 5 5 单位资源即可将总耗时缩短至 5 5 5 天。此时顿顿手中还剩余 4 4 4 单位资源,但无论如何安排,也无法使总耗时进一步缩短。
i | 基础耗时 | t i t_i ti缩减 1 1 1 天所需资源 | c i c_i ci 投入资源数量 | 实际耗时 |
---|---|---|---|---|
1 | 6 | 1 | 1 | 5 |
2 | 5 | 1 | 0 | 5 |
3 | 6 | 2 | 2 | 5 |
4 | 7 | 1 | 2 | 5 |
🐈⬛样例输入2
4 30 2
6 1
5 1
6 2
7 1
🐈⬛样例输出2
2
🐈⬛样例解释2
投入 20 20 20 单位资源,恰好可将所有区域开垦耗时均缩短为 k = 2 k=2 k=2 天;受限于 k k k,剩余的 10 10 10 单位资源无法使耗时进一步缩短。
🐈⬛子任务
70% 的测试数据满足: 0 < n 0 < n 0<n, t i , c i ≤ 100 t_i,c_i \leq 100 ti,ci≤100 且 0 < m ≤ 1 0 6 0 < m \leq 10^6 0<m≤106;
全部的测试数据满足: 0 < n 0 < n 0<n, t i , c i ≤ 1 0 5 t_i,c_i \leq 10^5 ti,ci≤105 且 0 < m ≤ 1 0 9 0 < m \leq 10^9 0<m≤109。
😸问题解决
🐈满分代码(含逐行代码解释)
🍭C++
#include<bits/stdc++.h>
using namespace std;
int main(){
long long int n, m, k;
cin >> n >> m >> k;
/*
int t[100001], c[100001];
int source[100001]; //source表示削减开垦时长所消耗的资源
*/
map<int, int>t, c, source;
for(int i = 0; i < n; i++){
cin >> t[i] >> c[i]; //输入
}
/*总耗时取决于耗时最长的区域!!!*/
int max; //表示开垦耗时最多的区域
for(int i = 0; i < n; i++){
if(t[i] > max){
max = t[i]; //遍历输入的开垦耗时,更新max为耗时的最大值
}
source[t[i]] += c[i]; //计算所有地块每缩减一天所需要的资源之和
}
for(int i = max; i > 0; i--){
//从最大开垦天数到最小开垦天数遍历
if(max == k){
break; //如果最大开垦天数为至少要开垦的天数,则无需任何计算,跳出循环
}
if(m > source[i]){
//m是顿顿手中的资源总数
m = m - source[i]; //更新每减少一天的开垦天数顿顿手中剩下的资源
source[i-1] += source[i]; //将第i天的开垦所需要的资源数量累加到第i-1天的资源数量上,因为此处i是由大到小遍历,所以i-1是i往后遍历的下一项
max--; //最大开垦天数减一,直到顿顿手中资源不够或者max == k
}
else break; //顿顿手中的资源不够时跳出循环
}
cout << max;
}
🍭Python
n, m, k = map(int, input().split())
t, c, source = {
}, {
}, {
}
for i in range(n):
ti, ci = map(int, input().split())
t[i], c[i] = ti, ci
max_t = 0
for i in range(n):
if t[i] > max_t:
max_t = t[i]
if t[i] not in source:
source[t[i]] = 0
source[t[i]] += c[i]
while max_t > k and m > 0:
if m >= source[max_t]:
m -= source[max_t]
if max_t-1 not in source:
source[max_t-1] = 0
source[max_t-1] += source[max_t]
max_t -= 1
else:
break
print(max_t)
🐈场景拓展
本题代码可以用于解决以下应用场景:
- 开垦问题:这段代码可以计算在给定资源情况下,开垦指定天数所需的最长时间。
- 资源分配问题:这段代码通过计算每个区域在不同时间段需要的资源数量,然后根据顿顿手中的资源总数,按照优先级分配资源。可以用于管理资源分配、调度或优化问题。
- 动态规划问题:该代码使用动态规划的思想,通过逐步更新状态,计算得到最优解。可以用于解决其他类似的动态规划问题,例如背包问题、路径规划等。