放假回家

Posted on Edited on In

题目大意：给定一个 N 个数的数列 a[i]和数字 M，对于每一个 i，计算出在 1~i-1 中，最多能选多少个数字，使得这些数字的和不超过 M-a[i]。

正解是权值线段树巴拉巴拉的，但是用对顶堆就可以卡过去

大根堆存储我们要去装的，小根堆存储我们没装的

代码如下：

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 1e5 + 66;

int T, n, m, sum;
int a[N];

priority_queue<int, vector<int>, greater<int> >yh;
priority_queue<int>q;

inline void yhm_clear()
{
    sum = 0;
    while (! q.empty()) q.pop();
    while (! yh.empty()) yh.pop();
    return;
}

inline void yhm_func()
{
    int i, j;
    n = read(), m = read();
    for (i = 1; i <= n; ++ i) a[i] = read();
    for (i = 1; i <= n; ++ i)
    {
        while (! yh.empty() && ! q.empty() && q.top() > yh.top())
        {
            yh.push(q.top());
            sum -= q.top();
            q.pop();
        }
        while (! yh.empty() && sum + yh.top() <= m - a[i])
        {
            sum += yh.top();
            q.push(yh.top());
            yh.pop();
        }
        if (sum <= m - a[i])
        {
            q.push(a[i]), sum += a[i];
            while (! yh.empty() && sum + yh.top() <= m)
            {
                sum += yh.top();
                q.push(yh.top());
                yh.pop();
            }
        }
        else
        {
            while (! q.empty() && sum > m - a[i])
            {
                sum -= q.top();
                yh.push(q.top());
                q.pop();
            }
            q.push(a[i]);
            sum += a[i];
        }
        put(yh.size());
    }
    return (void)(puts(""));
}

signed main()
{
    T = read();

    while (T --)
    {
        yhm_clear();
        yhm_func();
    }

    return 0;
}