茂港网站设计公司,现在哪些做进口商品的电商网站,深圳手机企业网站设计,推广资讯题目链接#xff1a;P1102 A-B 数对 - 洛谷
1.题目分析 2.算法原理
解法一#xff1a;暴力 - 两层for循环 因为这道题需要你在数组中找出来两个数#xff0c;让这两个数的差等于定值C就可以了#xff0c;一层for循环枚举A第二层for循环枚举B#xff0c;求一下看是否等于…题目链接P1102 A-B 数对 - 洛谷
1.题目分析 2.算法原理
解法一暴力 - 两层for循环 因为这道题需要你在数组中找出来两个数让这两个数的差等于定值C就可以了一层for循环枚举A第二层for循环枚举B求一下看是否等于C如果是的话就用一个计数器count但数据范围是2e5两层for循环下来就超时了a和c的数据范围是2的30次方加完之后会超出int所以一会要用long long来存
解法二先统计数组中每个数出现的次数接下来枚举所有的B然后找出C B出现的次数
原来是A-BC可以把B移到右边就是ACBC是一个定值A和B全是从数组中挑数出来的比如根据示例一C1也就是A1B数组[1123]枚举B等于1的话问题就变成了要看看数组里面有多少个数等于2B枚举第二个1的时候也是看数组里面有多少个2B枚举2的时候看数组中有多少个3B枚举3的时候看看数组里面有多少个4因此我们可以先统计数组中每个数出现的次数接下来枚举所有的B然后找出C B出现的次数如何快速找出CB出现的次数可以用哈希表来统计unordered_mapLL,LL第一个表示数第二个关键字表示次数在枚举B的过程中直接在哈希表中找C B出现的次数然后累加加起来就可以了这个思想就是把枚举的过程变成了查找的过程
代码
#include iostream
#include unordered_mapusing namespace std;typedef long long LL;
const int N 2e5 10;LL n, c;
LL a[N];
unordered_mapint, int mp; // 数该数出现的次数int main()
{cin n c;for (int i 1; i n; i){cin a[i];mp[a[i]]; //每个数出现的次数记录下来}LL ret 0;for (int i 1; i n; i){// b a[i]// 找 c a[i]ret mp[c a[i]]; //算出来的和的对应出现次数mp记录了a数组存的每个数}cout ret endl;return 0;
}
如果这道题c可以等于0在累加次数的代码附近加一个判断即可
#include iostream
#include unordered_map
using namespace std;typedef long long LL;
const int N 2e5 10;LL n, c;
LL a[N];
unordered_mapint, int mp; // 数该数出现的次数int main()
{cin n c;for (int i 1; i n; i){cin a[i];mp[a[i]]; //每个数出现的次数记录下来}LL ret 0;for (int i 1; i n; i){if (c){// b a[i]// 找 c a[i]ret mp[c a[i]]; //算出来的和的对应出现次数mp记录了a数组存的每个数}else ret mp[c a[i]] - 1;//c 0; 不减1算出来的结果是n * n; 比如a[3,3,3]结果是333 3*3 9//正确结果应是n*(n-1)/n*2(3-1) (3-1) (3-1) 6//a[1], 正确结果是0无法选择两个不同的元素 不减1算出来的结果是1 }cout ret endl;return 0;
}
