1 条题解
-
0
差值配对:解题说明
用
unordered_map<long long,long long>统计频数。对每个不同值 x,查找 x−C;若 C>0,贡献 freq[x]·freq[x−C],两个值不同,自然没有同一下标。若 C=0,必须扣除与自己配对的选择,贡献 freq[x]·(freq[x]−1)。将各贡献相加即可。reserve预留哈希表空间;find查询且不插入元素。键也使用 long long,因为 x−C 最低可达 −3000000000。求积前频数就是 long long,避免 32 位溢出。期望时间 O(n),空间 O(n)。哈希表在恶意碰撞下可能变慢;稳定复杂度替代方案是排序后,对每个元素用
lower_bound、upper_bound查找 x−C 的次数,并在 C=0 时扣一,时间 O(n log n)。常见错误:C=0 直接平方频数而包含 i=j;将有序对除以 2;用 int 保存答案;查询时随意使用
operator[]并在遍历中插入新键。验证期望由独立 Python 算法生成,不读取参考程序。样例先手算,再以空实现确认测试失败;正式数据包含边界、固定种子随机及两个最大规模用例。
C++17 参考实现
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; long long C; cin >> n >> C; unordered_map<long long, long long> freq; freq.reserve(2 * n + 1); for (int i=0;i<n;++i) { long long x; cin>>x; ++freq[x]; } long long answer=0; for (const auto &entry:freq) { long long x=entry.first, f=entry.second; auto it=freq.find(x-C); if (it!=freq.end()) answer+=f*(it->second-(C==0?1:0)); } cout << answer << '\n'; return 0; }
- 1
信息
- ID
- 5266
- 时间
- 2000ms
- 内存
- 256MiB
- 难度
- 2
- 标签
- 递交数
- 2
- 已通过
- 1
- 上传者