首页 > 代码库 > cf484B

cf484B

2024-08-03 07:51:07   220人阅读

H - Maximum Value
Time Limit:1000MS     Memory Limit:262144KB     64bit IO Format:%I64d & %I64u
Submit Status Practice CodeForces 484B
Appoint description: 

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

 

 二分真是太神了，，，枚举 一个数的倍数，最大的余数肯定是比他小，二分搜索比倍数小的数，，，，参考了网上大牛的解法，加了一个剪枝，不然会超时，无限YM
#include<iostream>#include<cstdio>#include<cstring>#include<string>#include<cmath>#include<cstdlib>#include<algorithm>#include<queue>#include<vector>#include<set>using namespace std;int a[200010];inline int mymax(int a,int b){    return a > b? a: b;}inline int bin_search(int l,int r,int val)//二分查找小于val的最大值{    int mid;    while(l<=r){        mid=(l+r)>>1;        if(a[mid]==val) return mid-1;        else if(a[mid]>val) r=mid-1;        else l=mid+1;    }    return r;}int main(){    int n;    while(~scanf("%d",&n)){        for(int i=0;i<n;i++)            scanf("%d",&a[i]);        sort(a,a+n);        int mmax = 0;        for(int i=0;i<n-1;i++){            if(a[i]!=a[i-1]){//剪枝。如果之前出现过了就不用查了；            int tmp=a[i]+a[i];            while(tmp<=a[n-1]){                int pos=bin_search(0,n-1,tmp);                mmax = mymax(mmax,a[pos]%a[i]);                tmp+=a[i];            }            mmax =mymax(mmax,a[n-1]%a[i]);            }        }        printf("%d\n",mmax);    }    return 0;}

　　

cf484B


联系
我们