双指针算法,70分(前三个样例) 求助!!!
查看原帖
双指针算法,70分(前三个样例) 求助!!!
524191
Man_CCNU楼主2021/11/9 10:54
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1e6 + 10;
int a[N], n, dis, res;

int main()
{
    cin >> n >> dis;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + n + 1);
    int cur = 1, ne = 1;
    while (ne <= n) {
        while (ne <= n&&a[ne] - a[cur] < dis) {//当小于dis时,一直循环
            ne++;
        }
        
        if (cur != ne){
            if (ne > n) {//ne指针越界特判
                ne = n;
                res += (ne - cur - 1);
                break;   //证明已经计算完,所以跳出
            }
            res += (ne - cur - 1);
        }

        cur = ne;
        ne++;
    }
    cout << res << endl;

    return 0;
}
2021/11/9 10:54
加载中...