题目描述

出题是一件痛苦的事情!
相同的题目看多了也会有审美疲劳,于是我舍弃了大家所熟悉的 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

题解

题目是数可以是重复的
比如样例可以是
4 0
4 4 4 4
10 3
1 1 1 2 2 3 3 3 4
首先我们先对整个序列进行排序 将连续的数"堆"在一起
我们每次去找符合条件的区间 可以大大减少时间开销

AC代码

#include <iostream>
#include <algorithm>
using namespace std;
int a[222222];
int main() {
    ios::sync_with_stdio(false);
    int n,c;
    while(cin >> n >> c)
    {
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
        }
        sort(a,a+n);
        long long res = 0;
        int l = 1,r = 1;
        for (int i = 0; i < n; ++i) {
            while(l<n&&a[l] - a[i]<c)l++;//找到等于目标的下标
            while(r<n&&a[r] - a[i]<=c)r++;//找到大于目标的下标
            if(a[l] - a[i] == c && a[r-1] - a[i] == c)//如果区间符合目标加上结果
                res += r - l;
        }
        cout << res << endl;
    }
    return 0;
}
Last modification:April 15th, 2020 at 10:22 pm
如果觉得我的文章对你有用,请随意赞赏