文章

8

粉丝

27

获赞

24

访问

698

头像
差分计数 题解:n诺测试数据太小了,正常暴力会超时,应该用字典。
P1907 华东师范大学2022年机试
发布于2025年3月12日 14:00
阅读数 21

n是10^6数量级,两层for循环暴力数量级10^12,但是计算机1s只能处理10^8。。。。。

 

这题实际考查找,应该用字典解答

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);  // 优化输入速度
    
    int n, x;
    cin >> n >> x;
    vector<int> a(n);
    unordered_map<int, int> map1;
    
    // 读取数组并统计频率,用于接下来的查找
    for (int j = 0; j < n; j++) {
        cin >> a[j];
        map1[a[j]]++;
    }
    
    long long sum = 0;
    // 因为a[i]-a[j]=x,所以a[i]=a[j]+x。读入a[j],假设输入的a数组序列中能找到满足=a[j]+x的a[i],自然i,j就是一对。
    //map存了每个a[j]的频率,只需要查找到等于a[j]+x的有几个,就是a[i]的个数,找到多少个a[i],自然就找到多少有序对
    for (int &num : a) {
        int target = num + x;  //遍历a数组的每个值(a[j]),计算出如果存在对应的a[...

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发