[基本練習]NOIP模擬題 ：數對的個數（A-B) dec 解題報告

Description

出題是一件痛苦的事情！

題目看多了也有審美疲勞，於是我捨棄了大家所熟悉的A+B Problem，改用A-B了哈哈！

好吧，題目是這樣的：給出一串數以及一個數字C，要求計算出所有A-B=C的數對的個數。（不同位置的數字一樣的數對算不同的數對）

Input Format

第一行包括2個非負整數N和C，中間用空格隔開。

第二行有N個整數，中間用空格隔開，作爲要求處理的那串數。

Output Format

輸出一行，表示該串數中包含的所有滿足A-B=C的數對的個數。

Sample Input

4 1

1 1 2 3

Sample Output

3

Data Limit

對於90%的數據，N <= 2000；

對於100%的數據，N <= 200000。

所有輸入數據都在longint範圍內。

 【分析】
絕對水題，直接模擬即可。由於最大數據是200000，O(n^2)的算法會超時，所以要用二分+數組壓縮進行優化。

【我的代碼】
用了二分，沒有用數組壓縮。
#include <cstdio>
#include <iostream>
#include <cstdlib>
using namespace std;
int N;
int C;
int A[200001];

int cmp(const void *a,const void *b) 
{ 
    return *((int *)a)-*((int *)b); 
}

int main()
{
   
    freopen("dec.in","r",stdin);
    freopen("dec.out","w",stdout);
    scanf("%d %d\n",&N,&C);
    for (int i=1;i<=N;i++)
        cin>>A[i];
    qsort(A+1,N,sizeof(int),cmp);
    int Tot=0;
    for (int i=1;i<=N;i++)
    {
        int s=1;
        int b=N;
        int need=A[i]-C;
        int mid;
       
        if(need<A[1] || need>A[N])
            continue;
        bool flag=false;
        while (s<b) 
        {     
            mid=(s+b)/2; 
            if(A[mid]==need)
            {
                flag=true;
                break;
            }
            if (A[mid]<need)  
                s=mid+1; 
            else  
                b=mid; 
        } 
       
        if(!flag)
            continue;
       
        for (int j=mid;j>=1;j--)
        {
            if(A[j]==need)
                Tot++;
            else
                break;
        }
        for (int j=mid+1;j<=N;j++)
        {
            if(A[j]==need)
                Tot++;
            else
                break;
        }
    }
    cout<<Tot<<endl;
   
    return 0;
}