Maximum Value二分二分 暴力暴力

D - Maximum Value Time Limit:1000MS    Memory Limit:262144KB    64bit IO Format:%I64d & %I64u Submit Status

Description

You are given a sequence a consisting of n integers. Find the maximum possible value of

(integer remainder of ai divided by aj), where 1 ≤ i, j ≤ n and ai ≥ aj.

Input

The first line contains integer n — the length of the sequence (1 ≤ n ≤ 2·105).

The second line contains n space-separated integers ai (1 ≤ ai ≤ 106).

Output

Print the answer to the problem.

Sample Input

Input

3
3 4 5
      

Output

2

題意：就是讓你求a[j] > a[i]下a[j]%a[i]的最大值
第一種思路：通常我們是對n個數進行暴力這樣的話肯定會逾時的，是以我們換個思路進行暴力，看每個數的最大為10^6，那麼我們就從2到最大的開始枚舉，輸入的時候處理為在第幾個數就是幾，然後進行暴力，
代碼：
       
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>

using namespace std;

int n;
int a[3000000];
int max1 = 2000000;

int main() {
    scanf("%d",&n);
    memset(a,0,sizeof(a));
    for(int i = 0; i < n; i++) {
        int d;
        scanf("%d",&d);
        a[d] = d;
    }
    for(int i = 2; i < max1; i++) {
        if(a[i] != i) {
            a[i] = a[i-1];
        }
    }//這個地方的處理就是說在找到a[i]的倍數的時候，确定他的前一位是最大比他小的數，
    int tol = 0;
    for(int i = 2; i < max1; i++) {
        if(a[i] == i) {
            for(int j = 2*i-1; j < max1; j += i) {
                if(a[j] > a[i]){
                  tol = max(tol,a[j]%a[i]);
                }
            }
        }
    }
    printf("%d\n",tol);
    return 0;
}
           
        
第二種思路是二分：每次找到a[i]的倍數大于等于的數的下标-1的數，然後進行判斷最大餘數
AC代碼：
       
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>

using namespace std;

int n;
int a[3000000];

int main() {
    scanf("%d",&n);
    memset(a,0,sizeof(a));
    for(int i = 0; i < n; i++) {
        scanf("%d",&a[i]);
    }
    sort(a,a+n);
    int tol = 0;
    for(int i = 0; i < n; i++) {
        if(i > 0 && a[i]==a[i-1]){
            continue;
        }
        int k = a[n-1]/a[i]+1;
        for(int j = 2; j <= k; j++) {
            int s = lower_bound(a+i,a+n,a[i]*j)-a-1;
            if(a[s]%a[i] > tol) {
                tol = a[s]%a[i];
            }
        }
    }
    printf("%d\n",tol);
    return 0;
}

二分二分，奇葩的東西！！！