自动搬运

查看原文

来自洛谷，原作者为

	TinyKiecoo **

搬运于2025-08-24 22:02:29，当前版本为作者最后更新于2018-12-19 21:22:35，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

我们首先想到的朴素算法就是根据$size$从大到小排序，枚举$f[i]$与$f[j]$，判断是否需要比较，时间复杂度约$O(n^2)$。

代码：

#include"cstdio"
#include"algorithm"
int n,s,f[100001];
bool cmp(int x,int y){
    return x>y;
}
int main(){
    scanf("%d",&n);
    for(register int i=1;i<=n;i++)scanf("%d",&f[i]);
    std::sort(f+1,f+1+n,cmp);
    for(register int i=1;i<=n;i++){
        for(register int j=i+1;j<=n;j++){
            if(f[j]>=0.9*f[i])s++;
        }
    }
    printf("%d",s);
}

但是纯暴力代码只能得$50$分，我们可以想办法优化。↓

我们把$size$从大到小排序后，则$f[x]>f[x+1]$。于是，若$f[i]×0.9>f[j]$，则$f[i]×0.9>f[j+1]$。换句话说，若$f[j]$不需比较，则$f[j]$之后的数也一定不需比较，所以我们可以先进行一个小优化，在第二层循环中，若$f[j]$不需要比较，则跳出当前循环，进行下一个循环。这样我们可以苟到$60$分。

代码：

#include"cstdio"
#include"algorithm"
int n,s,f[100001];
bool cmp(int x,int y){
    return x>y;
}
int main(){
    scanf("%d",&n);
    for(register int i=1;i<=n;i++)scanf("%d",&f[i]);
    std::sort(f+1,f+1+n,cmp);
    for(register int i=1;i<=n;i++){
        for(register int j=i+1;j<=n;j++){
            if(f[j]>=0.9*f[i])s++;
            else break;
        }
    }
    printf("%d",s);
}

我们可以想办法再次优化。↓

还是观察已从大到小排好序的$size$，若$f[i]×0.9<=f[j]$，则$f[i+1]×0.9<=f[j]$，也就是若$f[i]$需要与$f[j]$比较，则$f[i+1]$也一定必须与$f[j]$比较，那么我们可以记录一下位置$l$，表示上一次判断到哪里了，下一次直接从$l+1$开始判断，并且加上$l$与$i$相差的数量，时间复杂度$O(2n)$。

代码：

#include"cstdio"
#include"algorithm"
using namespace std;
int n;
long long s,l=1,f[100001];
inline bool cmp(long long x,long long y) {
    return x>y;
}
int main() {
    scanf("%d",&n);
    for(register int i=1; i<=n; i++)scanf("%lld",&f[i]);
    sort(f+1,f+1+n,cmp);
    for(register int i=1; i<=n; i++) {
        for(register int j=l+1; j<=n; j++){
            if(f[i]*9<=f[j]*10)l=j;
            else break;
        }
        s+=l-i;
    }
    printf("%lld",s);
}

$\mathbf{\color{red}\text{我只是蒟蒻，讲得不太好，大佬勿喷，谢谢}}$