cf 484B 二分+贪心

题目大意： 给定序列a ， 求a[i] % a[j] 得最大值（a[i] > a[j])

思路：最接近a[j]倍数的a[i]肯定更靠近最大答案，所以枚举所有a[j]倍数，二分找到最靠近倍数的数，然后比较即可。刚开始只找了2a[j]，，显然单纯了。。

#include <cstdio>
#include <string>
#include <cstring>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <iostream>
#include <iomanip>

using namespace std;
#define maxn 200055
#define MOD 1000000007
#define mem(a) memset(a , 0 , sizeof(a))
#define memx(a) memset(a , 0x7f , sizeof(a))
#define LL __int64
#define INF 999999999
int arr[maxn];

int solve(int val , int l , int r)
{
    int mid ;
    while(l <= r)
    {
        mid = (l + r ) / 2;
        if(arr[mid] == val) return mid - 1;
        else if(arr[mid] > val) r = mid - 1;
        else l = mid + 1;
    }
    return r;
}

int main()
{
    int n;
    while(scanf("%d" , &n) != EOF)
    {
        for(int i = 0 ; i < n ; i ++) scanf("%d" , &arr[i]);
        sort(arr , arr + n);
        int ans = 0;
        for(int i = 0 ; i < n ; i ++)
        {
            if(arr[i] != arr[i-1])
            {
                int tmp = arr[i] + arr[i];
                while(tmp <= arr[n-1])
                {
                    int pos = solve(tmp , 0 , n-1);
                    //cout << pos << endl;
                    ans = max(ans , arr[pos] % arr[i]);
                    tmp += arr[i];
                }
                ans = max(ans , arr[n-1] % arr[i]);
            }
        }
        printf("%d\n" , ans);
    }
    return 0;
}