pog loves szh II_(HDU-5265)

(两个数的和用二分接近mod)

题意：

给出n，p，n个数，从中取两个数 a，b ， 求出（ a + b ）% p 的最大值。

解析：

先把每个数%p , 可以发现两个数加起来，要么 < p，要么 ≥ p，然后小于 2p。 
那么对于大于p的，必定是最大那两个数加起来%p，满足贪心的。 

小于p的话，就可以直接找，二分可以，因为满足单调性。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100005;
ll n,p,a[N];
inline void read(ll &x) {
    int flag = 0;
    x = 0;
    char c = getchar();
    if(c == '-')
        flag = 1;
    while(c < '0' || c > '9') {
        if(c == '-')
            flag = 1;
        c = getchar();
    }
    while(c >= '0' && c <= '9')
        x = x * 10 + c - '0', c = getchar();
    if(flag) x = -x;
}
int main() {
    while(~scanf("%lld%lld", &n, &p)) {
        ll maxz = 0;
        for(int i = 0; i < n; i++) {
            read(a[i]);
            a[i] %= p;
            maxz = max(maxz, a[i]);
        }
        sort(a, a+n);

        ll ans = (a[n-1] + a[n-2]) % p;
        for(int i = 0; i < n-1; i++) {
            ll val = p - a[i] - 1;
            int pos = upper_bound(a, a+i-1, val)-a-1;
/* 对于upper_bound来说，返回的是被查序列中第一个大于查找值的指针，也就是返回指向被查值>查找值的最小指针，
lower_bound则是返回的是被查序列中第一个大于等于查找值的指针，也就是返回指向被查值>=查找值的最小指针。 */
            if(pos == -1) {
                ans = max(ans, (a[i] + maxz) % p);
            }else {
                ans = max(ans, (a[pos] + a[i]) % p);
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}