C - Sigma Problem
https://atcoder.jp/contests/abc353/tasks/abc353_c
思路
暴力TLE
观察 a1 a2 ... an 序列
计算目标是, 两两结合并并求 模
sum = sigma (ai + aj)%1e8
ai , aj <= 1e8
ai + aj 可能溢出,也可能不溢出
于是我们考虑, 统计所有溢出的个数。
对数组进行排序,
从左到右依次遍历, 对于每个元素x, lower_bound寻找其右边大1e8-x第一个元素位置,
计算得到 此为止到序列末尾 都是溢出的贡献, 进行累计。
最后定义不考虑溢出的总和
sum = sigma (ai + aj)
答案 = sum - 溢出总贡献 * 1e8
Code
https://atcoder.jp/contests/abc353/submissions/53397070
int n; vector<long long> a; const long long base = 1e8; int main() { cin >> n; a.resize(n); long long sum = 0; for(int i=0; i<n; i++){ cin >> a[i]; sum += a[i]; } long long total = (n-1) * sum; sort(a.begin(), a.end()); long long cnt = 0; for(int i=0; i<n; i++){ long long complement = base - a[i]; // Search for first element x such that complement ≤ x auto lower = lower_bound(a.begin()+i+1, a.end(), complement); if (lower == a.end()){ continue; } int lower_index = lower - a.begin(); int great_cnt = n - lower_index; cnt += great_cnt; } long long minus_num = cnt*base; long long ans = total - minus_num; cout << ans << endl; return 0; }
标签:ai,sum,aj,long,1e8,Problem,Sigma,溢出 From: https://www.cnblogs.com/lightsong/p/18187572