知道multiset就是简单签到，不知道就是…
Find the answer
Problem Description
Given a sequence of $n$ integers called $W$ and an integer $m$. For each $i (1 \leq i \leq n)$, you can choose some elements $W_k (1 \leq k < i)$, and change them to zero to make $\sum_{i=1}^{i}W_j \leq m $. So what’s the minimum number of chosen elements to meet the requirements above?.
Input
The first line contains an integer $Q$ —- the number of test cases.
For each test case:
The first line contains two integers $n$ and $m$ —- $n$ represents the number of elemens in sequence $W$ and $m$ is as described above.
The second line contains $n$ integers, which means the sequence $W$.
Output
For each test case, you should output $n$ integers in one line: $i-th$ integer means the minimum number of chosen elements $W_k (1 \leq k < i)$, and change them to zero to make $ \sum_{j=1}^{i}W_j \leq m$.
Sample Input
2
7 15
1 2 3 4 5 6 7
5 100
80 40 40 40 60
Sample Output
0 0 0 0 0 2 3
0 1 1 2 3
如果知道stl里面的multiset的话…
“模拟判断，然后把当前值插入，再while()把不合法的直接删除，因为当前这个数不合法以后就不会用了。”
代码如下：
1 |
|
如果不知道stl里面的multiset的话…
那就要老老实实二分或者离散化+线段树
标准答案离散化+线段树的做法：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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
using namespace std;
double pi=acos(-1);
long long int a[200010],number[200010<<2],number2[200010<<2],bz[200010<<2],bz2[200010<<2];
struct node
{
int id;
long long int b;
/* data */
} no[200010];
bool cmp(const node &fi,const node &se)
{
if(fi.b==se.b) return fi.id<se.id;
return fi.b<se.b;
}
int to[200010];
void PushUp(int rt)
{
number[rt]=number[rt*2];
if(number[rt*2+1]>number[rt]) number[rt]=number[rt*2+1];
}
void build(int l,int r,int rt)
{
bz[rt]=0;
number[rt]=0;
bz2[rt]=0;
if(l==r)
{
number[rt]=0;
number2[rt]=0;
return;
}
int mid=(l+r)/2;
build(l,mid,rt*2);
build(mid+1,r,rt*2+1);
PushUp(rt);
}
void pushdown(int rt,int l,int r)
{
int mid=(l+r)/2;
if (bz[rt])
{
bz[rt*2]+=bz[rt];
bz[rt*2+1]+=bz[rt];
number[rt*2]+=(bz[rt]);
number[rt*2+1]+=(bz[rt]);
bz[rt]=0;
}
if(bz2[rt])
{
bz2[rt*2]+=bz2[rt];
bz2[rt*2+1]+=bz2[rt];
number2[rt*2]+=(bz2[rt]);
number2[rt*2+1]+=(bz2[rt]);
bz2[rt]=0;
}
}
void change(long long int o,int L,int R,int l,int r,int rt)
{
if(L>R) return;
if(l==r)
{
number[rt]+=o;
number2[rt]+=1;
return;
}
if(L<=l&&R>=r)
{
number[rt]+=o;
bz[rt]+=o;
bz2[rt]+=1;
return;
}
int mid=(l+r)/2;
pushdown(rt,l,r);
if(L<=mid) change(o,L,R,l,mid,rt*2);
if(R>mid) change(o,L,R,mid+1,r,rt*2+1);
PushUp(rt);
}
long long int query(long long int k,int l,int r,int rt)
{
if(l==r) return number2[rt];
int mid=(l+r)/2;
pushdown(rt,l,r);
int ans;
if(number[rt*2]>k) ans=query(k,l,mid,rt*2);
else ans=query(k,mid+1,r,rt*2+1);
PushUp(rt);
return ans;
}
int main()
{
int t;
scanf("%d",&t);
while (t--)
{
int n=1,m=1;
scanf("%d %d",&n,&m);
build(1,n+1,1);
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
no[i].b=a[i];
no[i].id=i;
}
sort(no+1,no+n+1,cmp);
change(1e9,n+1,n+1,1,n+1,1);
for(int i=1;i<=n;i++)
to[no[i].id]=i;
for(int i=1;i<=n;i++)
{
long long int k=query(m-a[i],1,n+1,1);
printf("%lld ",i-k);
change(a[i],to[i],n+1,1,n+1,1);
}
printf("\n");
}
return 0;
}