双指针做法,复杂度O(nlogn),为什么#2#3#4TLE?
查看原帖
双指针做法,复杂度O(nlogn),为什么#2#3#4TLE?
671260
Nekomusume楼主2022/8/22 18:40
#include <iostream>
#include <algorithm>
using namespace std;

int a[200010];

int main()
{
    int n, c;
    cin >> n >> c;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    sort(a + 1, a + n + 1);
    long long ans = 0;
    for(int i = 1; i <= n; i++)
    {
        int l = 1, r = 1;
        while(a[i] - a[l] > c && l < i)
        {
            l++;
        }
        while(a[i] - a[r] >= c && r < i)
        {
            r++;
        }
        if(a[i] - a[l] == c)
        {
            ans += r - l;
        }
    }
    cout << ans << endl;
    return 0;
}

2022/8/22 18:40
加载中...