二分答案和贪心。

Table of Contents

  1. Description
  2. Solution

Description

给定一个正整数序列 $A[1] \ldots A[n]$,
求一个不下降正整数序列 $B[1] \ldots B[n]$,
使得 $Max\{|A[j] - B[j]|, 1 \le j \le n\}$ 最小.

Solution

直接求解很难, 而且时限也不短, 我们改为验证.

贪心的考虑, 一定是让前面的数字尽可能小,
对于一个 $mid$, 在不小于上一个元素的情况下,
一定是加/减到上一个元素为止.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;

typedef long long ll;

const int maxn = 5e+6 + 6;

int n;
ll a[maxn], tmp[maxn];
ll A, B, C, D, p;

ll f(int x)
{
    ll q = 1ll;
    for(int i = 1; i <= 3; ++i) q = (q * x) % p;
    q = (q * A) % p;
    ll s = 1ll;
    for(int i = 1; i <= 2; ++i) s = (s * x) % p;
    s = (s * B) % p;
    ll l = (C * x) % p;
    ll ret = (q + s) % p;
    ret = (ret + l) % p;
    return (ret + D) % p;
}
inline bool chk(ll mid)
{
    memcpy(tmp, a, sizeof a);
    tmp[1] = max(tmp[1] - mid, 1ll);
    for(register int i = 2; i <= n; ++i)
    {
        if(tmp[i] > tmp[i - 1])
            tmp[i] = max(tmp[i] - mid, tmp[i - 1]);
        else if(tmp[i] < tmp[i - 1])
        {
            if(tmp[i] + mid >= tmp[i - 1]) tmp[i] = tmp[i - 1];
            else return false;
        }
    }
    return true;
}

int main()
{
    scanf("%d%lld%lld%lld%lld%lld%lld", &n, &A, &B, &C, &D, &a[1], &p);
    //printf("%lld ", a[1]);
    for(register int i = 2; i <= n; ++i)
        a[i] = (f(a[i - 1]) + f(a[i - 2])) % p;// printf("%lld ", a[i]);
    //putchar('\n');
    ll l = 0, r = 1e+9, ans = 0;
    while(l <= r)
    {
        ll mid = (l + r) >> 1;
        if(chk(mid)) ans = mid, r = mid - 1;
        else l = mid + 1;
    }
    printf("%lld\n", ans);
    return 0;
}

Thanks to $\LaTeX$