P7072. 直播获奖

发表于 分类于 阅读次数： Waline： 本文字数： 146 阅读时长 ≈ 1 分钟

考点

  • 排序

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
const int maxn = 650;
int n, w, a[maxn];

int main() {
  int x, cnt;
  cin >> n >> w;
  for (int i = 1; i <= n; ++i) {
    cin >> x, ++a[x];
    cnt = max(1, i * w / 100);
    for (int j = 600; j >= 0; --j) {
      if (cnt <= a[j]) {
        cout << j << " ";
        break;
      }
      cnt -= a[j];
    }
  }
  return 0;
}

思路

每次插入都要求有序，如果数字过大必须考虑平衡树！

很可惜这里数字最大只有600，采用计数排序；

每次计算最少的获奖个数cnt，从600开始往下累减人数，直到cnt小于等于某数的个数为止。