cf 568 div2

题意：

有n个学生要考试，总的考试时间是M，每个学生考试需要\(t_i\)的时间，每次只能一个学生进行考试。问如果学生要完成考试，那么在他前面至少有多少人不能参加考试？

题解：

就是求一个序列前面最多多少个数相加少于等于（ m - \(a_i\) ）

c1数据范围比较小，然后今天又恰好看到了小灰公众号讲了插入排序，就用上了。保证\(a_i\)前面的序列是有序的，然后从后往前一直减，直到符合要求。但是时间复杂度是O(\(n^2\)),c2的数据是肯定过不了的，然后我没想到怎么写！！看了题才发现\(t_i\)<=100，可以直接记录\(t_i\)的数量，然后从小到大扫一遍，时间复杂度O(n100)(2 \(10^6\))

//c1#include 
    
     int main() {    int n, m, a[110], sum = 0;    scanf("%d %d", &n, &m);    for(int i = 0; i < n; i++) {        int cnt = 0;        scanf("%d", &a[i]);        if(sum > m - a[i]) {            int summ = sum, j = i - 1;            while(summ > m - a[i]) {                cnt++;                summ -= a[j];                j--;            }        }        int b = a[i], j = i - 1;        if(i) {            while(b < a[j] && j >= 0) {                a[j+1] = a[j];                j--;            }            a[j+1] = b;        }        sum += b;        printf("%d ", cnt);    }    printf("\n");    return 0;}
    

//c2#include 
    
     int cnt[110];int main() {    int n, m, a, sum = 0;    scanf("%d %d", &n, &m);    for(int i = 0; i < n; i++) {        scanf("%d", &a);        sum += a;        int ans = 0;        if(sum > m) {            int summ = a;            for(int i = 1; i <= 100; i++) {                if(cnt[i]) {                    if(summ + cnt[i] * i < m) {                        ans += cnt[i];                        summ += cnt[i] * i;                    }                    else {                        ans += (m - summ) / i;                        break;                    }                }            }        }        else ans = i;        cnt[a]++;        printf("%d ", i - ans);    }    return 0;}