Average Rank Kattis – averagerank ( 前缀和-思维-模拟）

题目链接

https://vjudge.net/problem/Kattis-averagerank

题目大意

n个人m天，每天有k个人会获得一分，问每个人的平均排名。

代码

#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef long double ld;

ll last_updated[300030];
ll sum_of_ranks[300030];
ll current_rank[300030];

ll points[300030];
ll old_sum[300030];
ll answer[300030];

int n,d;

ll get_sum(int p, ll t){
    return sum_of_ranks[p] + current_rank[p] * (t - last_updated[p]);//旧前缀和加上新的排名的部分
}

int main()
{
    cin >> n >> d;
    for(ll c1 = 0; c1 < d; c1++){
        int k;
        cin >> k;
        for(int c2 = 0; c2 < k; c2++){
            int i;
            cin >> i;
            i--;
            answer[i] += get_sum(points[i], c1) - old_sum[i];//将发生变化的部分累加到ans
            sum_of_ranks[points[i]] = get_sum(points[i], c1);//得分为points[i]的rank前缀和
            last_updated[points[i]] = c1;//得分为points[i]的最后修改
            current_rank[points[i]]++;//得分为points[i]的排名
            points[i]++;//得分加一
            old_sum[i] = get_sum(points[i], c1);//i号人的上次更新时的rank前缀和
        }
    }

    for(int c1 = 0; c1 < n; c1++){
        answer[c1] += get_sum(points[c1],d) - old_sum[c1];
        cout << setprecision(6) << fixed << double(answer[c1]) / double(d) + 1.0 << "\n";
    }

    return 0;
}