C - Sum of Numbers Greater Than Me
https://atcoder.jp/contests/abc331/tasks/abc331_c
思路
由于 值 可以是重复的, 需要记录每出现的值 对应的位置 , 记录在 map<int, vector<int>> valpos;
此处利用了map key的自动排序属性, 把所有值 进行从小到大 做了排序,
然后根据valpos,将每个值计算 前缀和, 记录在 map<int, long long> valsum;
每个值的和 = 值 * 出现的次数
最后根据前缀和valsum, 计算每个位置 的答案(大于此位置值的所有值的和), 记录在 long long ABiggerSum[1000010];
打印 long long ABiggerSum[1000010];
Code
https://atcoder.jp/contests/abc331/submissions/48138824
int N; int A[1000010]; map<int, vector<int>> valpos; map<int, long long> valsum; long long ABiggerSum[1000010]; int main() { cin >> N; for(int i=1; i<=N; i++){ cin >> A[i]; valpos[A[i]].push_back(i); } map<int, vector<int>>::iterator it, itprev; for(it=valpos.begin(); it!=valpos.end(); it++){ int thisval = it->first; vector<int> indice = it->second; long long thissum = thisval * indice.size(); if (it == valpos.begin()){ valsum[it->first] = thissum; } else { valsum[it->first] = valsum[itprev->first] + thissum; } itprev = it; } long long total = valsum[itprev->first]; for(it=valpos.begin(); it!=valpos.end(); it++){ int thisval = it->first; vector<int> indice = it->second; long long thissum = valsum[thisval]; long long biggersum = total - thissum; for(auto one_pos: indice){ ABiggerSum[one_pos] = biggersum; } } for(int i=1; i<=N; i++){ cout << ABiggerSum[i] << " "; } return 0; }
标签:Me,map,valpos,valsum,Sum,long,int,Than,first From: https://www.cnblogs.com/lightsong/p/17876164.html