题目链接
题意：
有n个学生依次答题，每个学生都有自己的答题时长。答题总时间只有M分钟。问第 i 个学生要答题，则前面最少多少人不答题才行？
分析：
由题面我们可以知道t较小，因此无需使用主席树（而且主席树会TLE，/(ㄒoㄒ)/~~）。
代码：
#include <bits/stdc++.h>
using namespace std
;
const int maxn
= 2e5 + 9;
int a
[maxn
], sum
[maxn
];
int in
[101];
int main()
{
ios
::sync_with_stdio(false);
cin
.tie(0);
int n
, m
;
cin
>> n
>> m
;
for (int i
= 0; i
< n
; i
++)
{
cin
>> a
[i
];
}
sum
[0]=a
[0];
for (int i
= 1; i
< n
; i
++)
{
sum
[i
] =a
[i
]+ sum
[i
- 1];
}
in
[a
[0]]++;
cout
<< 0 << ' ';
for (int i
= 1; i
< n
; ++i
)
{
int zan
= sum
[i
- 1], b
= m
- a
[i
];
if (zan
<= b
)
{
cout
<< 0 << ' ';
}
else
{
int ans
= 0;
for (int j
= 100; j
> 0; --j
)
{
if (in
[j
])
{
int sz
= in
[j
];
int jian
= sz
* j
;
if (zan
- b
> jian
)
{
ans
+= sz
;
zan
-= jian
;
}
else
{
ans
+= (zan
- b
) / j
;
if ((zan
- b
) % j
)
++ans
;
break;
}
}
}
cout
<< ans
<< ' ';
}
in
[a
[i
]]++;
}
return 0;
}
