有一個a數組，里面有n個整數。現在要從中找到兩個數字(可以是同一個)?ai,aj?，使得?ai?mod?aj?最大并且?ai?≥?aj。
Input
單組測試數據。
第一行包含一個整數n，表示數組a的大小。(1?≤?n?≤?2*10^5)
第二行有n個用空格分開的整數ai?(1?≤?ai?≤?10^6)。 Output
輸出一個整數代表最大的mod值。 Input示例
3
3?4?5 Output示例
2
題解：首先考慮mod的真正定義
a%b=a/b*b+c
思考一下其實是kb+c的形式，畫在數軸上就是
很顯然，如果有一個數x%a>b%a他肯定會在(k*a+b,(k+1)*a)的區間之中，到底有沒有這些數存在可以用前綴和O(1)查詢
所以因此我們就可以對c即余數進行二分了，不過二分的時候檢驗是O(nlogn)的，因為會枚舉每一個數的倍數的區間，總復雜度大約是調和級數即logn 但其實仔細一想這是不滿的
在套上二分，復雜度是O(nlognlogn)?
調和級數時間復雜度、代碼如下：
#pragma GCC optimize("inline",3) #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std;int vis[4000010],sum[4000010],k,n,a[200010],cnt;int check(int x) {for(register int i=1;i<=cnt;++i){for(register int j=a[i];j<=1e6;j+=a[i]){if(sum[j+a[i]-1]-sum[j+x-1]>0){return 1;}}}return 0; }int main() {scanf("%d",&n);int tmp;for(register int i=1;i<=n;++i){scanf("%d",&tmp);if(!vis[tmp]){vis[tmp]=1;}}for(register int i=1;i<=2e6;++i){sum[i]=sum[i-1]+vis[i];}for(int i=1;i<=1e6;i++){if(vis[i]){a[++cnt]=i;}}register int l=0,r=2e6,mid;while(l<r){int mid=(l+r)>>1;if(check(mid)){l=mid;}else{r=mid-1;}if(r-l<=1){r=check(r)?r:l;break;}}printf("%d\n",r); }
這個程序1e5跑跑是非常輕松的但是到了2e5就有點力不從心了
直接提交到51nod上就大概只能過18個點
于是考慮優化，其實只要知道了上面那個mod的定義，我們每次對于(k+1)*ai找到小于它的最大aj，那么這個aj%ai的值肯定是(k*ai,(k+1)*ai)區間內所有數%ai最大的
因此我們可以先預處理出f[i]為比i小的最大ai，然后在向上面一樣枚舉區間對于每個區間計算最大模數更新答案，因為省去了二分，復雜度就是O(nlogn)
代碼如下：
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std;int b[2000010],a[200010],n,t,ans=-1;int cmp(int a,int b) {return a>b; }int main() {scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}sort(a+1,a+n+1,cmp);int t=unique(a+1,a+n+1)-a-1;n=t;int j=1;for(int i=2e6;i>=1;i--){while(j<=n&&a[j]>=i) j++;b[i]=a[j];} for(int i=1;i<=n;i++){for(int j=2;j<=2e6/a[i];j++){ans=max(ans,b[a[i]*j]%a[i]);}}printf("%d\n",ans); }
求解最大非空子數組的時間復雜度，?
?
yzy大佬用set隨手A掉了此題
詳見這里
https://blog.csdn.net/yzyyylx/article/details/81013038