AT_abc388_c 题解

ikunTLE · 2025-01-12 05:10:13 · 题解

题目传送门

思路

可以使用双指针解决此题。

首先将序列按升序排序。用两个循环变量，i 在左，j 在右，则 A_i 表示上面的麻薯，A_j 表示下面的麻薯。每一次寻找最小的 A_j 满足 A_i\le\frac{A_j}{2}，那么 i 到 j 的区间全部满足要求，故将答案增加 j-i+1 即可。

由于 i 和 j 只会向后移动，时间复杂度为 N 级别，最大时间复杂度来自排序，为 \mathcal{O}(N\log N)，可以通过此题。

AC CODE

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read(){int x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
const int N=5e5+10;
int a[N];
signed main(){
    int n=read();
    for(int i=1;i<=n;++i)
        a[i]=read();
    sort(a+1,a+n+1);
    int ans=0;
    for(int i=1,j=1;i<=n;++i){
        while(j<=n&&a[i]*2>a[j])
            ++j;
        ans+=n-j+1;
    }
    printf("%lld\n",ans);
    return 0;
}