题意很好理解,就是让你搞到两个数a[i],a[j]使得a[i]>a[j]且a[i]%a[j]最大,然后把最大值输出来.

然后,我就开始乱搞了,时间复杂度有点高,O(n*sqrt(max(a[i]));

很容易得出一个结论 如果a[i]>a[j]且a[i]/p==a[j]/p那么a[j]%p>a[j]%p.

那么就开始乱搞了枚举p,如果全部枚举了复杂度就变成O(n*max(a[i]))了.

我们可以只枚举p*p<a[i]的部分,剩下的肯定是连续的1.2.3.4...p.语文不好,不知道这么讲,总之枚举sqrt(a[i])就行了.

#include <cstdio>#include <cstring>#include <algorithm>#include <iostream>#define N 200000using namespace std;int a[N+20],ans,b[N+20];int main(){    int m;    scanf("%d",&m);    for (int i=1;i<=m;i++) scanf("%d",&b[i]);    sort(b+1,b+1+m);    int n = 0;    for (int i=1;i<=m;i++){        if (b[i]!=b[i-1]) a[++n] = b[i];    }    ans = 0;    for (int j=1;j<=1000;j++){        int lef = n, rig = n - 1;        for (int i=n;i>=1;i--){            if (j*j>a[i]) break;            for (;a[lef-1]*(j+1)>a[i];lef--);            if (lef<=rig&&a[i]%a[lef]>ans) ans = a[i]%a[lef];            rig = lef - 1;        }    }    for (int i=1;i<=n;i++){        for (int j=n;j>=1&&1LL*a[i]*a[i]<=a[j];j--){            if (a[j]%a[i]>ans) ans = a[j]%a[i];        }    }    printf("%d\n",ans);    return 0;}

Codeforces Round #276 (Div. 1)Maximum Value