AT_abc388_e 题解

· · 题解

题目传送门

思路

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

首先考虑答案最大的情况，那就是每一个麻薯都能与另一个配对，答案为 \lfloor\frac{N}{2}\rfloor。

序列已经按照升序排序。为了使答案最大，我们用两个指针，i 从 1 开始，j 从一半（\lfloor\frac{N}{2}\rfloor+1）开始遍历。这样做一定能使答案最大，比如若 j 过于靠前会导致前面数不足，反之若靠后会导致后面的数不足，无法使答案最大化。遍历时，若 A_i\le\frac{A_j}{2}，说明满足条件，继续向后遍历，将 i 和 j 都增加 1，同时答案增加 1；否则说明 A_j 不够大，只将 j 增加 1。

由于 i 和 j 只会向后移动，时间复杂度为 \mathcal{O}(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 hn=n/2,ans=0;
    for(int i=1,j=hn+1;i<=hn&&j<=n;){
        if(a[i]*2<=a[j])
            ++i,++j,++ans;
        else ++j;
    }
    printf("%lld\n",ans);
    return 0;
}