题解 P4670 【[BalticOI 2011 Day2]Plagiarism】

TinyKiecoo · 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);
}