本文共 2688 字,大约阅读时间需要 8 分钟。
原文转载:
C2. Exam in BerSU (hard version)
The only difference between easy and hard versions is constraints.
If you write a solution in Python, then prefer to send it in PyPy to speed up execution time.
A session has begun at Beland State University. Many students are taking exams.
Polygraph Poligrafovich is going to examine a group of n students. Students will take the exam one-by-one in order from 1 -th to n -th. Rules of the exam are following:
Students take the exam in the fixed order, one-by-one, without any interruption. At any moment of time, Polygraph Poligrafovich takes the answer from one student.
The duration of the whole exam for all students is M minutes (maxti≤M ), so students at the end of the list have a greater possibility to run out of time to pass the exam.
For each student i , you should count the minimum possible number of students who need to fail the exam so the i -th student has enough time to pass the exam.
For each student i , find the answer independently. That is, if when finding the answer for the student i1 some student j should leave, then while finding the answer for i2 (i2>i1 ) the student j student does not have to go home.
Input
The first line of the input contains two integers n and M (1≤n≤2⋅105 , 1≤M≤2⋅107 ) — the number of students and the total duration of the exam in minutes, respectively.
The second line of the input contains n integers ti (1≤ti≤100 ) — time in minutes that i -th student spends to answer to a ticket.
It's guaranteed that all values of ti are not greater than M .
Output
Print n numbers: the i -th number must be equal to the minimum number of students who have to leave the exam in order to i -th student has enough time to pass the exam.
题意:这题困难版就是一个可能会让你超时的问题,我就被卡了第14组(实在太弱),然后在这上面找题解,发现一位大佬写的较为简便的方法,因为每个人的时间都被限制在100以内,所以我们可以用一个数组来记录所有的数出现的次数,这样我们每次判断这个同学能通过考试所需最少不及格同学人数时,我们只需要尽可能地从小到大取掉最大足够小的时间的同学,最后得到的答案必然是最小。下面附上代码。
#includeusing namespace std;int number[105];int main(){ int n,m; int t,ans,sum,x; scanf("%d%d",&n,&m); memset(number,0,sizeof(number)); for(int i=1; i<=n; i++) { scanf("%d",&t); ans=0; sum=m-t; for(int j=1; j<=100; j++) { x=min(sum/j,number[j]); ans+=x; sum-=x*j; } number[t]++; printf("%d ",i-1-ans); }}