当前位置：首页 > article >正文

202303-2-垦田计划

article 2025/3/1 16:00:01

一、题目分析

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

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;
}

查看全文

http://www.kler.cn/a/104696.html