Codeforces 1185C2 Exam in BerSU (hard version)

发表于 | 阅读次数：

题目链接

题意：

有n个学生依次答题，每个学生都有自己的答题时长。答题总时间只有M分钟。问第 i 个学生要答题，则前面最少多少人不答题才行？

分析：

由题面我们可以知道t较小，因此无需使用主席树（而且主席树会TLE，/(ㄒoㄒ)/~~）。

代码：

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
#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;
}
0%