当前位置: 首页> 教育> 高考 > 抖音小程序定制_王爷王妃貌美还狠凶_seo网上培训_百度经验悬赏令

抖音小程序定制_王爷王妃貌美还狠凶_seo网上培训_百度经验悬赏令

时间:2025/7/14 22:35:24来源:https://blog.csdn.net/qq_23311271/article/details/142691018 浏览次数:0次
抖音小程序定制_王爷王妃貌美还狠凶_seo网上培训_百度经验悬赏令

P1102 A-B 数对 - 洛谷 | 计算机科学教育新生态

题目来源

洛谷

题目内容

A-B 数对

题目背景

出题是一件痛苦的事情!

相同的题目看多了也会有审美疲劳,于是我舍弃了大家所熟悉的 A+B Problem,改用 A-B 了哈哈!

题目描述

给出一串正整数数列以及一个正整数 C C C,要求计算出所有满足 A − B = C A - B = C AB=C 的数对的个数(不同位置的数字一样的数对算不同的数对)。

输入格式

输入共两行。

第一行,两个正整数 N , C N,C N,C

第二行, N N N 个正整数,作为要求处理的那串数。

输出格式

一行,表示该串正整数中包含的满足 A − B = C A - B = C AB=C 的数对的个数。

样例 #1

样例输入 #1

4 1
1 1 2 3

样例输出 #1

3

提示

对于 75 % 75\% 75% 的数据, 1 ≤ N ≤ 2000 1 \leq N \leq 2000 1N2000

对于 100 % 100\% 100% 的数据, 1 ≤ N ≤ 2 × 1 0 5 1 \leq N \leq 2 \times 10^5 1N2×105 0 ≤ a i < 2 30 0 \leq a_i <2^{30} 0ai<230 1 ≤ C < 2 30 1 \leq C < 2^{30} 1C<230

2017/4/29 新添数据两组

知识点

哈希|二分

题目思路

  1. 利用哈希的O(1)的查询快速得出结果
    将问题转化成:在哈希表内能否找到两个数字A 和 B 相减起来等于 C
    先存好A 利用 B = A - C 遍历查找是否存在于哈希表中
  2. 利用 A - B = C 转化成 A = B + C
    将B+C存到哈希表中 查找A 是否存在
  3. 二分计算满足条件(大于等于b+c)的元素数量 并减去满足条件(小于b+c)的元素数量 得出 B + C = A 的个数 然后计数

AC代码

解法一:哈希 + 查重计数 + 枚举 B

//
// Created by Jisam on 28/09/2024 11:34 PM.
// Solution of  A-B 数对
// 2024-09-28 23:38:23 AC 100 哈希 + 查重计数
#include <bits/stdc++.h>#define  int long long
using namespace std;signed main() {cin.tie(nullptr)->sync_with_stdio(false);// 读取输入的整数n和c的值int n, c;cin >> n >> c;// 初始化一个长度为n的整数数组avector<int> a(n);// 初始化计数器cnt为0,用于后续计算符合条件的对数int cnt = 0;// 初始化一个无序映射maps,用于统计数组a中每个元素出现的次数unordered_map<int, int> maps;// 遍历数组a,读取每个元素的值,并在maps中更新对应值的出现次数,同时将元素的值减去cfor (auto &x : a) {cin >> x;maps[x] += 1; x -= c;  }// 遍历数组a,累计maps中每个元素出现的次数,计算符合条件的对数for (int i = 0; i < n; i++) {cnt += maps[a[i]];}// 输出符合条件的对数cout << cnt << endl;return 0
}

解法二:哈希 + 查重计数+ 枚举 A

//
// Created by Jisam on 28/09/2024 11:34 PM.
// Solution of  A-B 数对
// 2024-09-28 23:49:03 AC 100 哈希 + 查重计数
#include <bits/stdc++.h>#define  int long long
using namespace std;signed main() {cin.tie(nullptr)->sync_with_stdio(false);// 读取输入的整数n和c,分别代表数组长度和待加常量int n, c;cin >> n >> c;// 初始化长度为n的整型数组avector<int> a(n);// 初始化计数器cnt,用于统计结果int cnt = 0;// 初始化哈希表maps,用于快速查找数组中每个元素加c后的出现次数unordered_map<int, int> maps;// 遍历数组a,读取每个元素并更新哈希表for (auto &x : a) {cin >> x;// 增加元素加c后在哈希表中的计数maps[x + c] += 1;}// 遍历数组a,累加每个元素加c后在数组中出现的次数到cntfor (int i = 0; i < n; i++) {cnt += maps[a[i]];}// 输出最终的累加结果cntcout << cnt << endl;return 0
}

解法三:二分 * 2

//
// Created by Jisam on 28/09/2024 11:34 PM.
// Solution of  A-B 数对
// 2024-10-03 13:08:15 AC 100 二分 * 2
#include <bits/stdc++.h>#define  int long long
using namespace std;signed main() {cin.tie(nullptr)->sync_with_stdio(false);// 输入变量n和c的值int n, c;cin >> n >> c;// 初始化一个大小为n的整数数组avector<int> a(n);int cnt = 0;// 通过cin依次输入数组a的每个元素的值for (auto &B: a) {cin >> B;}// 对数组a进行排序,以便后续处理sort(a.begin(), a.end());// 遍历排序后的数组a,计算每个元素满足条件的元素数量for (auto B: a) {// 计算满足条件(大于等于b+c)的元素数量,并减去满足条件(小于b+c)的元素数量 得出 B + C  = A 的个数cnt += ((upper_bound(a.begin(), a.end(), B + c) - a.begin()) - (lower_bound(a.begin(), a.end(), B + c) - a.begin()));}// 输出满足条件的元素总数cout << cnt << endl;return 0
}
关键字:抖音小程序定制_王爷王妃貌美还狠凶_seo网上培训_百度经验悬赏令

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: