pog loves szh II

HDOJ-5265-pog loves szh II

分析

x​′​​=x%p∈[0,p−1]。

x​′​​+y​′​​∈[0,2p−2]。

当x​′​​+y​′​​∈[0,p−1]时，利用双指针扫描法求最大的x​′​​+y​′​​，记为z​1​′​​。

当x​′​​+y​′​​∈[p,2p−2]，即(x​′​​+y​′​​)%p∈[0,p−2]时，取最大的x​′​​+y​′​​，记为z​2​′​​。

答案为max(z​1​′​​,z​2​′​​%p)。

实现

#include <iostream>
#include <algorithm>
using namespace std;

typedef long long LL;
const int N = 100010;
int n, p;
int a[N];

int main () {
    while (cin >> n >> p) {
        for (int i = 1; i <= n; ++ i) cin >> a[i];

        for (int i = 1; i <= n; ++ i) a[i] %= p;
        sort(a + 1, a + n + 1);
        LL res = ((LL)a[n - 1] + a[n]) % p; // 可能是第二种情况

        for (int i = 1, j = n; i <= n; ++ i) {
            while (j > i && (LL)a[i] + a[j] >= p) -- j;
            if (i != j) {
                res = max(res, (LL)a[i] + a[j]);
            } else {
                break;
            }
        }
        cout << res << endl;
    }
    return 0;
}