A21238. 符文的共鸣
填空题
困难
知识点
题目描述
符文的共鸣
题目描述
在魔法世界中，有 n 个符文，每个符文有一个能量值 ai。当两个符文共鸣时，会产生能量，但能量过高时会溢出，只保留剩余部分。
具体来说，符文 i 和符文 j 共鸣产生的能量为 (ai + aj) mod 100000000。
请计算所有不同的符文对（即所有 i < j 的配对）共鸣能量的总和。
输入格式
第一行输入一个整数 n。
第二行输入 n 个整数 a1, a2, ……, an。
输出格式
输出一个整数，表示所有符文对共鸣能量的总和。
输入样例1
2
1 1输出样例1
2输入样例2
2
99999999 99999999输出样例2
99999998数据范围
2≤N≤100000，1≤ai≤108。
参考答案
#include<iostream>
#include<algorithm>
long long s[300005];
long long a[300005];
long long ans = 0;
int main(){
int n;
std::cin >> n;
const long long mod = 1e8;
for(int i = 1 ; i <= n ; i++){
std::cin >> a[i];
}
std::sort(a + 1 , a + n + 1) ;
for(int i = n ; i >= 1 ; i--){
s[i] = s[i+1] + a[i];
}
for(int i = 1 ; i <= n ; i++){
ans += (n - i) * a[i] + s[i+1] ;
int t = 0;
t = std::lower_bound(a + i + 1 , a + n + 1 , mod - a[i]) - a;
t = n - t + 1;
ans -= t * mod;
}
std::cout << ans;
}
上一题
下一题