202303

202303

一、题目分析

本题可以采用模拟法去做，通过循环判断每一轮的最大耗时需要消耗的资源数，直到资源耗尽。
但注意到任务要求：

70% 的测试数据满足：0<n,ti,ci<=100 。且0<m<=10^6
全部的测试数据满足：0<n,ti,ci<=10^5 。且0<m<=10^9

按照上述模拟法，假设最坏情况每一天都遍历，总共有n个工程，每个工程ti天，最坏10⁵*10⁵=10¹⁰>10⁹，因此会超时。

二、正确题解

采取类似于前缀和的思路。先把相同天数看成一个整体，他们所需要的总资源记在数组中，如果全部资源m满足最大天数需要资源要求，那么即可减小一天，此时最大天数-1，其所需资源需要累加到前一天。

三、代码展示©

#include <stdio.h>
#include <stdlib.h>
int nrr[100001];
int main(){int n,m,k,i;scanf("%d%d%d",&n,&m,&k);int MAX=0;for(i=0;i<n;i++){int day,source;scanf("%d%d",&day,&source);nrr[day]+=source;if(MAX<day){MAX=day;}}while(1){if(MAX<=k){break;}if(m>=nrr[MAX]){m-=nrr[MAX];nrr[MAX-1]+=nrr[MAX];MAX--;}else{break;}}printf("%d",MAX);return 0;
}