CSP认证 202303-2 垦田计划 优化之后的方法 100分题解

看了博客里大佬的做法，可以考虑到不用每次都去遍历那个时间所需资源数的数组或者列表，因为每次想要让整体时间缩短，就考虑所需天数最大的，当天数最大的不唯一时，比如样例中，开始需要6天的就有两个，所以想要让整体工期从6天到5天，就需要把所有6天的资源都给足才可以，代码里用到了cost数组，cost[i]表示所有需要i天才能完成的任务，想要缩短，所需要的资源总数（所有的都加起来）

#include<iostream>
using namespace std;
const int N = 100010;
int cost[N] = {0};                      //cost[i]表示的是还需要i天完成的所有任务都想缩短需要的资源数 
int main(){
	long long m,n,k,maxday = 0;
	cin >> n >> m >> k;
	for(int i = 0; i < n; i++){
		int dayNum,c;
		cin >> dayNum >> c;
		cost[dayNum] += c;
		if(dayNum > maxday){              //用maxday记录当前最长的时间 
			maxday = dayNum; 
		}
	} 
	
	while((maxday > k) && (m >= cost[maxday])){         
	    //两种情况下不能继续调整，第一个是已经达到了要求的最短开垦时间，第二个是当前剩余资源已经不够再减一天了 
		int maxCost = cost[maxday];
		m -= maxCost;                        //调整剩余资源数 
		
		maxday--; 
		cost[maxday] += maxCost;          
	} 
	
	cout << maxday;
	
	return 0;
}