【202303-2】垦田计划

Attention：

这道题当时思路错了，无法得全分。
后来考完和同学交流时，才发现如下的简便思路，即用标志数组记录耗时为i天的区域降低一天的总花费，然后从高向低降。

#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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30