[Blog] [Docs] [Code] [Slides] [About]

NWERC 2019 A - Average Rank

前缀和

2020-03-26 16:37 CST

Problem

题目链接(CodeForces)

题目要求:计算$w$轮比赛中$n$个人的排名平均值。

关键思想:前缀和。

  • 用前缀和保存某个得分的累计名次,并记录这个值最后的更新时间和增长速度。
  • 当一个人离开这个得分时
    • 更新这个得分的排名
    • $O(1)$处理这个得分的累计名次
    • $O(1)$处理下一个得分的累计名次
    • $O(1)$处理这个人的排名总和(加上他在这个得分时的增量)

Solution

#include <bits/stdc++.h>
using namespace std;
 
int n = 0, w = 0, maxs = 0;
long long rk[300005] = {};
long long updated[300005] = {};
long long prefix[300005] = {};
long long score[300005] = {};
long long total[300005] = {};
 
int main() {
  scanf("%d%d", &n, &w);
  rk[0] = 1, updated[0] = 1;
  for (int t = 1; t <= w; ++t) {
    int len = 0, cur = 0;
    scanf("%d", &len);
    while (len--) {
      scanf("%d", &cur);
      int s = score[cur];
      ++score[cur];
      if (s + 1 > maxs) {
        maxs = s + 1;
        rk[maxs] = 1, prefix[maxs] = 0, updated[maxs] = t;
      }
      prefix[s] += rk[s] * (t - updated[s]);
      rk[s] = rk[s] + 1, updated[s] = t;
      total[cur] += prefix[s];
      prefix[s+1] += rk[s+1] * (t - updated[s+1]);
      updated[s+1] = t;
      total[cur] -= prefix[s + 1];
    }
    //printf("round %d\n", t);
    //for (int s = 0; s <= maxs; ++s) {
    //  printf("%d: rk %d @ %d => psum %d (+= %d)\n", s, rk[s], updated[s], prefix[s], rk[s] * (t - updated[s]));
    //}
    //for (int i = 1; i <= n; ++i) printf("%d ", total[i]);
    //printf("\n============\n");
  }
  for (int s = 0; s <= maxs; ++s) {
    prefix[s] += rk[s] * (w+1 - updated[s]);
    //printf("%d: rk %d @ %d => psum %d\n", s, rk[s], updated[s], prefix[s]);
  }
  for (int i = 1; i <= n; ++i) total[i] += prefix[score[i]];
  //for (int i = 1; i <= n; ++i) printf("%d ", total[i]);
  //printf("\n============\n");
  for (int i = 1; i <= n; ++i) {
    printf("%.8lf\n", ((double)total[i]) / w);
  }
  return 0;
}
<EOF>