CCF-CSP真题《202303-2 垦田计划》思路+python，c++满分题解

蔚落 2023-10-13 09:12 15阅读 0赞

> 想查看其他题的真题及题解的同学可以前往查看：[CCF-CSP真题附题解大全][CCF-CSP]

--------------------

<table> 
 <tbody> 
  <tr> 
   <td>试题编号：</td> 
   <td>202303-2</td> 
  </tr> 
  <tr> 
   <td>试题名称：</td> 
   <td>垦田计划</td> 
  </tr> 
  <tr> 
   <td>时间限制：</td> 
   <td>1.0s</td> 
  </tr> 
  <tr> 
   <td>内存限制：</td> 
   <td>512.0MB</td> 
  </tr> 
  <tr> 
   <td>问题描述：</td> 
   <td> <h3>问题描述</h3> <p>顿顿总共选中了&nbsp;n&nbsp;块区域准备开垦田地，由于各块区域大小不一，开垦所需时间也不尽相同。据估算，其中第&nbsp;i&nbsp;块（1≤i≤n）区域的开垦耗时为&nbsp;ti&nbsp;天。这&nbsp;n&nbsp;块区域可以同时开垦，所以总耗时&nbsp;tTotal&nbsp;取决于耗时最长的区域，即：tTotal=max{t1,t2,⋯,tn}</p> <p>为了加快开垦进度，顿顿准备在部分区域投入额外资源来缩短开垦时间。具体来说：</p> 
    <ul> 
     <li> <p>在第&nbsp;i&nbsp;块区域<strong>每</strong>投入&nbsp;ci&nbsp;单位资源，便可将其开垦耗时缩短&nbsp;1&nbsp;天；</p> </li> 
     <li> <p>耗时缩短天数以整数记，即第&nbsp;i&nbsp;块区域投入资源数量必须是&nbsp;ci&nbsp;的整数倍；</p> </li> 
     <li> <p>在第&nbsp;i&nbsp;块区域最多可投入&nbsp;ci×(ti−k)&nbsp;单位资源，将其开垦耗时缩短为&nbsp;k&nbsp;天；</p> </li> 
     <li> <p>这里的&nbsp;k&nbsp;表示开垦一块区域的最少天数，满足&nbsp;0&lt;k≤min{t1,t2,⋯,tn}；换言之，如果无限制地投入资源，所有区域都可以用&nbsp;k&nbsp;天完成开垦。</p> </li> 
    </ul><p>现在顿顿手中共有&nbsp;m&nbsp;单位资源可供使用，试计算开垦&nbsp;n&nbsp;块区域最少需要多少天？</p> <h3>输入格式</h3> <p>从标准输入读入数据。</p> <p>输入共&nbsp;n+1&nbsp;行。</p> <p>输入的第一行包含空格分隔的三个正整数&nbsp;n、m&nbsp;和&nbsp;k，分别表示待开垦的区域总数、顿顿手上的资源数量和每块区域的最少开垦天数。</p> <p>接下来&nbsp;n&nbsp;行，每行包含空格分隔的两个正整数&nbsp;ti&nbsp;和&nbsp;ci，分别表示第&nbsp;i&nbsp;块区域开垦耗时和将耗时缩短&nbsp;1&nbsp;天所需资源数量。</p> <h3>输出格式</h3> <p>输出到标准输出。</p> <p>输出一个整数，表示开垦&nbsp;n&nbsp;块区域的最少耗时。</p> <h3>样例输入1</h3> 
    <blockquote> 
     <p>4 9 2<br> 6 1<br> 5 1<br> 6 2<br> 7 1</p> 
    </blockquote> <h3>样例输出1</h3> 
    <blockquote> 
     <p>5</p> 
    </blockquote> <h3>样例解释</h3> <p>如下表所示，投入&nbsp;5&nbsp;单位资源即可将总耗时缩短至&nbsp;5&nbsp;天。此时顿顿手中还剩余&nbsp;4&nbsp;单位资源，但无论如何安排，也无法使总耗时进一步缩短。</p> 
    <table> 
     <thead> 
      <tr> 
       <th>i</th> 
       <th>基础耗时&nbsp;ti</th> 
       <th>缩减&nbsp;1&nbsp;天所需资源&nbsp;ci</th> 
       <th>投入资源数量</th> 
       <th>实际耗时</th> 
      </tr> 
     </thead> 
     <tbody> 
      <tr> 
       <td>1</td> 
       <td>6</td> 
       <td>1</td> 
       <td>1</td> 
       <td>5</td> 
      </tr> 
      <tr> 
       <td>2</td> 
       <td>5</td> 
       <td>1</td> 
       <td>0</td> 
       <td>5</td> 
      </tr> 
      <tr> 
       <td>3</td> 
       <td>6</td> 
       <td>2</td> 
       <td>2</td> 
       <td>5</td> 
      </tr> 
      <tr> 
       <td>4</td> 
       <td>7</td> 
       <td>1</td> 
       <td>2</td> 
       <td>5</td> 
      </tr> 
     </tbody> 
    </table><h3>样例输入2</h3> 
    <blockquote> 
     <p>4 30 2<br> 6 1<br> 5 1<br> 6 2<br> 7 1</p> 
    </blockquote> <h3>样例输出2</h3> 
    <blockquote> 
     <p>2</p> 
    </blockquote> <h3>样例解释</h3> <p>投入&nbsp;20&nbsp;单位资源，恰好可将所有区域开垦耗时均缩短为&nbsp;k=2&nbsp;天；受限于&nbsp;k，剩余的&nbsp;10&nbsp;单位资源无法使耗时进一步缩短。</p> <h3>子任务</h3> <p>70%&nbsp;的测试数据满足：0&lt;n,ti,ci≤100&nbsp;且&nbsp;0&lt;m≤106；</p> <p>全部的测试数据满足：0&lt;n,ti,ci≤105&nbsp;且&nbsp;0&lt;m≤109。</p> </td> 
  </tr> 
 </tbody> 
</table>

**真题来源：**[矩阵运算][Link 1]

> 感兴趣的同学可以如此编码进去进行练习提交

**思路讲解：**

> 这道题也不难，使用标志数组记录耗时为i天的区域降低一天的总花费，然后从高向低降，最后就可以得出答案了。

**c++满分题解：**

#include<bits/stdc++.h>
    #include<iostream>
    using namespace std;
    
    int n, k;
    long long int m;
    map<int, int>tim, res, flag;
    
    int main(){
        cin >> n >> m >> k;
    
        int max = 0;
        for(int i = 0; i < n; ++i){
            cin >> tim[i] >> res[i];
            max = max > tim[i] ? max : tim[i];
            flag[tim[i]] += res[i];     
            // flag[i]为用时i天的区域缩短一天所用时
        }
        for(int i = max; i > 0; i--){
            //cout << i << " " << flag[i] << endl;
            if(max == k)break;
            if(m > flag[i]){
                m = m - flag[i];
                flag[i - 1] += flag[i];
                max--;
            }else break;
        }
        cout << max;
        return 0;
    }

**运行结果：**

![35ab05d8eb884006a5ef731a1156f60e.png][]

[CCF-CSP]: https://blog.csdn.net/weixin_53919192/article/details/124893395?spm=1001.2014.3001.5502
[Link 1]: http://118.190.20.162/view.page?gpid=T169
[35ab05d8eb884006a5ef731a1156f60e.png]: https://img-blog.csdnimg.cn/35ab05d8eb884006a5ef731a1156f60e.png