Gym-100676E Time Limit Exceeded?

原题链接 https://odzkskevi.qnssl.com/1110bec98ca57b5ce6aec79b210d2849?v=1491063604

**********************************************************************************************************************

题意:选择v[i]里的两个数相减的绝对值小于32，问你有多少对这样的数

解题思路：看题目就知道暴力枚举肯定会超时XD;

　　　　　所以就标记一下v[i]，每一次找v[i]前后31个数，看看有多少个, 减去重复的，就是答案。

**********************************************************************************************************************

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 10000+10;
int num[maxn];
int a[maxn];
int sum[maxn];
int vis[maxn];
int main()
{
    int T;
    cin >> T;
    while(T--){
        memset(a, 0, sizeof(a));
        memset(num, 0, sizeof(num));
        memset(vis, 0, sizeof(vis));
        int n, i, ans=0;
        cin >> n;

        for(i=0;i<n;i++){
            cin >> a[i];
            num[a[i]]++;
        }
        sum[0]=0;
        for(i=1;i<maxn;i++)//通过前缀和的方法求出有多少个符合
            sum[i]=sum[i-1]+num[i];
//        for(i=1;i< 150 ;i++)
//            cout << i << " " << sum[i] << endl;
        for(i=0;i<n;i++){
            int x = a[i];
            int rightn=min(10000, x+31);//只往右边跑，避免左右一起跑出现重复
            if(!vis[x]){
                ans+=num[x] * (sum[rightn] - sum[x]);//加上[x,x+31]的数的个数
                ans+=num[x]*(num[x]-1)/2;//如果同一个数出现了多次,C(2, n)个
                vis[x]=1;
            }
        }
        cout << ans  << endl;
    }
    return 0;
}