大前端

前端学习之家-大前端

洛谷P1102 A-B 数对(A+B Problem)

题目描述

出题是一件痛苦的事情!

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

好吧,题目是这样的:给出一串数以及一个数字 CC,要求计算出所有 A - B = CA−B=C 的数对的个数(不同位置的数字一样的数对算不同的数对)。

输入格式

输入共两行。

第一行,两个整数 N, CN,C。

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

输出格式

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

输入输出样例

输入 

4 1
1 1 2 3

输出 

3

说明/提示

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

对于 100\%100% 的数据,1 \leq N \leq 2 \times 10^51≤N≤2×105。

保证所有输入数据绝对值小于 2^{30}230。

思路

以该题目为例,找有多少个数对能满足A-B=C(其中A、B未知,C已知),对于一个式子来说,要找两个都未知的数字组合起来等于一个常数,这听起来就比较困难,所以我们对式子做个变形A-C=B,也就是说在数组中去找那些数字A减去一个常量等于另外一个数。(想法尝试)
关于此题的纯暴力方法,就是O(n2)两个for循环遍历,这肯定会超时,我们就想能不能优化只用一个for循环,遍历一次得到结果。
那我们就尝试遍历A,在遍历A的同时去查找B,这里就有一个使用map的方法能打到此效果
map用来装数组中每个数出现的次数,即map<int int> = map<数组元素,出现次数>
最后我们就遍历整个数组,累加每个数据(A)+C的结果的map映射值(B),如果存在B就有具体的值,没有B就是0,所以最后的和就是我们想要的答案

AC代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
map<ll,ll> ma;

int main()
{
    int n;
    ll c;
    cin>>n>>c;
    ll a[n+5];
    for(int i=0; i<n; i++)
    {
        cin>>a[i];
        ma[a[i]]++;
    }
    ll cnt=0;
    for(int i=0; i<n; i++)
    {
        cnt += ma[a[i]+c];
    }
    cout<<cnt;
    return 0;
}

发表评论:

Copyright Your WebSite.Some Rights Reserved.