卡3 TLE 用的优化枚举+快排 求大佬们带带
  • 板块P1102 A-B 数对
  • 楼主telankesi
  • 当前回复9
  • 已保存回复9
  • 发布时间2022/12/31 20:13
  • 上次更新2023/10/24 05:59:33
查看原帖
卡3 TLE 用的优化枚举+快排 求大佬们带带
866969
telankesi楼主2022/12/31 20:13
#include <stdio.h>
#include <time.h>
#define int long long
int a[200010];
void fun(int l,int r) {
    if (l >= r)return;
    else {
        int k = rand()%(r-l+1)+l;
        int t = a[k];
        a[k] = a[l];
        a[l] = t;
        int x = l;
        int y = r;
        while (x != y) {
            while (a[y] >= t && x < y) 
                y--;
            while (a[x] <= t && x < y)x++;
            if (x < y) {
                int m = a[x];
                a[x] = a[y];
                a[y] = m;
            }
        }

        a[l] = a[x];
        a[x] = t;
        fun(l, x - 1);
        fun(x + 1, r);
    }
}
int main() {
    int n,c;
    srand((unsigned)time(NULL));
    scanf("%lld %lld", &n,&c);//a-b=c
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
    }
    fun(1,n);
    int num = 0;
    int l = 1, r = 1;
    int t;
    for (int i = 1; i <= n; i++) {
         t = a[i]+c;

        while (  r <= n&& a[r] <= t) { r++; }
        while (l<=n&& a[l] < t) { l++; }

            num += r - l;

    }
    printf("%lld", num);
    return 0;
}
2022/12/31 20:13
加载中...