• CCF计算机资格认证模拟题202303-2垦田计划


    问题描述

    顿顿总共选中了

    块区域准备开垦田地,由于各块区域大小不一,开垦所需时间也不尽相同。据估算,其中第 块()区域的开垦耗时为 天。这 块区域可以同时开垦,所以总耗时 取决于耗时最长的区域,即:

    为了加快开垦进度,顿顿准备在部分区域投入额外资源来缩短开垦时间。具体来说:

    • 在第

    块区域投入 单位资源,便可将其开垦耗时缩短

    • 天;

    • 耗时缩短天数以整数记,即第

    • 块区域投入资源数量必须是
    • 的整数倍;

    • 在第

    • 块区域最多可投入 单位资源,将其开垦耗时缩短为
    • 天;

    • 这里的

    • 表示开垦一块区域的最少天数,满足 ;换言之,如果无限制地投入资源,所有区域都可以用
      • 天完成开垦。

      现在顿顿手中共有

      单位资源可供使用,试计算开垦

      块区域最少需要多少天?

      输入格式

      从标准输入读入数据。

      输入共

      行。

      输入的第一行包含空格分隔的三个正整数

      、 和

      ,分别表示待开垦的区域总数、顿顿手上的资源数量和每块区域的最少开垦天数。

      接下来

      行,每行包含空格分隔的两个正整数 和 ,分别表示第 块区域开垦耗时和将耗时缩短

      天所需资源数量。

      输出格式

      输出到标准输出

      输出一个整数,表示开垦

      块区域的最少耗时。

      样例输入1

      1. 4 9 2
      2. 6 1
      3. 5 1
      4. 6 2
      5. 7 1

      Data

      样例输出1

      5

      Data

      样例解释

      如下表所示,投入

      单位资源即可将总耗时缩短至 天。此时顿顿手中还剩余

      单位资源,但无论如何安排,也无法使总耗时进一步缩短。

      基础耗时 缩减 天所需资源
      投入资源数量实际耗时
      16115
      25105
      36225
      47125

      样例输入2

      1. 4 30 2
      2. 6 1
      3. 5 1
      4. 6 2
      5. 7 1

      Data

      样例输出2

      2

      Data

      样例解释

      投入

      单位资源,恰好可将所有区域开垦耗时均缩短为 天;受限于 ,剩余的

      单位资源无法使耗时进一步缩短。

      子任务

      的测试数据满足: 且

      全部的测试数据满足:

      且 。

    1. #include <iostream>
    2. using namespace std;
    3. #include <map>
    4. // 按照从大到小的方式排列
    5. map<int,int,greater<int>> u_map;
    6. int main(int argc, char const *argv[])
    7. {
    8. int n,m,k;
    9. int i;
    10. int t,c;
    11. cin >> n >> m >>k;
    12. for (i = 0; i < n; i++){
    13. scanf("%d%d",&t,&c);
    14. u_map[t]+=c;
    15. }
    16. map<int,int>::iterator it;
    17. // 取天数最大的那一类田地
    18. it = u_map.begin();
    19. t = (*it).first;
    20. c = (*it).second;
    21. // 特判
    22. if (t <= k){
    23. cout << k << endl;
    24. return 0;
    25. }
    26. while (c <= m && m > 0){
    27. // 耗费c单位的资源,使天数减少1
    28. u_map[t-1] += c;
    29. m -= c;
    30. u_map.erase(t);
    31. t = t-1;
    32. // 要保证k是最小开垦天数
    33. if (t <= k){
    34. break;
    35. }
    36. c = u_map[t];
    37. }
    38. cout << max(t,k);
    39. return 0;
    40. }

  • 相关阅读:
    URL、域名和网址的区别
    力扣刷题day42|121买卖股票的最佳时机、122买卖股票的最佳时机II
    《洛谷深入浅出基础篇》——P3405 citis and state ——哈希表
    VS2019无法设置Qt版本解决方案
    C#调用Python脚本
    Synopsys EDA Tools 安装问题记录
    计算机网络-传输层
    Trie字典树
    Redis常见数据类型及其常用命令详解
    【spring】Spring Bean 的作用域之间有什么区别?
  • 原文地址:https://blog.csdn.net/qq_65628600/article/details/133916074