[HEOI2014]南园满地推轻絮

思路：

就是二分去找\(\max(x)\), 满足\(|a_i-b_i|\le x\)

那么就是要让\(b_i\)尽可能小的满足\(a_i-b_i<x\)，然后在保证\(b_i\)单调不下降的情况下，不等式是否成立

易证：

当\(x > y\)时，若\(b_i\)数组满足条件\(a_i-b_i\le y\)且\(b_i\)单调不下降，那么\(b_i\)数组也一定满足\(a_i-b_i\le y\)且\(b_i\)单调不下降

那么有了这个性质就可以二分答案了，因为当小的取值成立时，大的取值一定成立

Code

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 5e6 + 10;

int n, sa, sb, sc, sd, p;
int l, r, ans, a[maxn], b[maxn];

inline int f(int x)
{
    return (1ll * sa * x  % p * x % p * x % p + 1ll * sb * x % p * x % p + 1ll * sc * x % p + sd) % p;
}

inline bool Check(int x)
{
    b[1] = max(0, a[1] - x);
    for (int i = 2; i <= n; ++i)
    {
        b[i] = max(b[i - 1], a[i] - x);
        if (abs(b[i] - a[i]) > x) return 0;
    }
    return 1;
}

int main()
{
    scanf ("%d %d %d %d %d %d %d", &n, &sa, &sb, &sc, &sd, a + 1, &p);
    for (int i = 2; i <= n; ++i) a[i] = (f(a[i - 1]) + f(a[i - 2])) % p, r = max(r, a[i]);
    r = max(a[1], r);
    while (l <= r)
    {
        int mid = (l + r) >> 1;
        if (Check(mid)) ans = mid, r = mid - 1;
        else l = mid + 1;
    }
    printf ("%d\n", ans);
}