题目链接
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;
}