C2. Exam in BerSU (hard version)(思维 + 小数据范围)
Problem - C2 - Codeforces
简单版本和困难版本之间的唯一区别是约束。
如果你用Python写一个解决方案，那么最好用PyPy发送，以加快执行时间。
波利格拉夫维奇要对N个学生进行考试。学生们将按照从第1个到第n个的顺序逐一参加考试。考试的规则如下：
第i个学生随机选择一张票。
如果这张票对学生来说太难，他就不回答，并立即回家（这个过程非常快，以至于被认为没有时间流逝）。这个学生没有通过考试。
如果这个学生认为这张票很容易，他花了整整十分钟来通过考试。之后，他立即得到一个分数并回家。
学生按照固定的顺序，一个接一个地参加考试，没有任何干扰。在任何时候，Polygraph Poligrafovich都会从一个学生那里获得答案。
所有学生的整个考试时间是M分钟(maxti≤M)，所以排在最后的学生有更大的可能用尽时间通过考试。
对于每个学生i，你应该计算出需要失败的学生的最小可能数量，以便第i个学生有足够的时间通过考试。
对于每个学生i，独立地找到答案。也就是说，如果在为学生i1寻找答案时，一些学生j应该离开，那么在为i2寻找答案时（i2>i1），学生j不必回家。
输入
输入的第一行包含两个整数n和M（1≤n≤2⋅105，1≤M≤2⋅107）--分别是学生人数和考试的总时间（分钟）。
输入的第二行包含n个整数ti (1≤ti≤100 )--第i个学生回答一张票所花的时间，以分钟计。
保证ti的所有值都不大于M。
Examples
input
Copy
7 15 1 2 3 4 5 6 7
output
Copy
0 0 0 0 0 2 3
input
Copy
5 100 80 40 40 40 60
output
Copy
0 1 1 2 3
输出
打印n个数字：第i个数字必须等于为了使第i个学生有足够的时间通过考试而必须离开考试的最小人数。
题解:
本来是直接用优先队列写的,好像确实会t,(用队列即使是t了,也可能会报WA)
正确思路是统计目前ti每种有多少,由于t<=100
每个ti,直接从1~100小到大看最多能放几个,(贪心来讲)肯定是小的放的越多越好,
#include <cstdio>
#include <cstring>
#include <algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<cmath>
#include<queue>
using namespace std;
typedef long long ll;
#define int long long
typedef pair<int,int> PII;
const int N = 1e6 + 10;
int a[104];
void solve()
{int n,m;cin >> n >> m;for(int i = 1;i <= n;i++){int x;cin >> x;int cnt = m - x;int ans = 0;for(int j = 1;j <= 100;j++){int p = min(cnt/j , a[j]);cnt -= p*j;ans += p;}cout <<i - 1 - ans <<" ";a[x]++;}
}signed main()
{
// ios::sync_with_stdio(0);
// cin.tie(0);cout.tie(0);int t = 1;
// cin >> t;while(t--){solve(); }
}
