牛客小白月赛81

小辰的智慧树

思路：我们可以发现，对于一颗树，若我们一次将其砍掉 x ，那么我将其每次砍去 1 ，然后砍 x 次获得的价值的相同，那么我们可以统计，对于每个高度，我们可以砍到这个高度的树有多少颗，又因为题目给出了树的初始高度和最低高度，那么由此可以想到差分，然后从最高处开始砍即可。

#include 

using namespace std;
const int N = 1e6 + 5;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef array<ll, 3> p3;
int mod = 1e9 + 7;
const int maxv = 4e6 + 5;
// #define endl "\n"

ll d[N];

void solve()
{
    ll n,m;
    cin>>n>>m;
    vector<int> h(n+5),w(n+5);
    for(int i=1;i<=n;i++){
        cin>>h[i]>>w[i];
        int r=h[i],l=w[i];
        d[l+1]++,d[r+1]--;
    }
    for(int i=1;i<N;i++) d[i]+=d[i-1];
    ll ans=0;
    for(ll i=N-1;i>=0;i--){
        ans+=min(m,d[i])*(i*2-1);
        m-=min(m,d[i]);
    }
    cout<<ans<<endl;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    t = 1;
//     cin>>t;
    while (t--)
    {
        solve();
    }
    system("pause");
    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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47