[HEOI2014]南园满地堆轻絮-题解

题目描述
小 Z 是 ZRP（Zombies’ Republic of Poetry，僵尸诗歌共和国）的一名诗歌爱好者，最近他研究起了诗词音律的问题。
在过去，诗词是需要编成曲子唱出来的，比如下面这首《菩萨蛮》，唱出来的话其对应的音符就是这样的：
南 园 满 地 堆 轻 絮， 愁 闻 一 霎 清 明 雨
1 1 5 5 6 6 5 4 4 3 3 2 2 1
因而可以发现，“1 1 5 5 6 6 5 4 4 3 3 2 2 1”这串音符就成为了研究音律的关键。
小Z翻阅了众多史料发现，过去的一首曲子的音调是不下降的
小Z想要知道对于一首给定的曲子，如何通过提高音调或者降低音调，将它的音调修改的不下降， 而且使得修改幅度最大的那个音符的修改幅度尽量小。
即如果把一个包含 n 个音 符的曲子看做是一个正整数数列 A[1]…A[n]， 那么 目标是求另一个正整数数列 B[1]…B[n]， 使得对于任意的 1 ≤ i < n 有 B[i] ≤ B[i+1]， 而且使得 Ans = Max{|A[j]-B[j]|,1 ≤ j ≤ n}尽量小。
小 Z 很快就想清楚了做法，但是鉴于他还忙着写诗， 所以这个任务就交给了你。

思路：简单二分就行。先生成数组，然后二分差值，将数组的最大值设置为上界，下界设为0，然后对于每次可能的差值进行check，数组前面的元素在合法的情况下越小越好，当出现元素比上一个元素小很多时，就返回false。
代码：

#include <bits/stdc++.h>
using namespace std;
long long A[10000050],n,sa,sb,sc,sd,Mod,l=0,r=0;
long long F(long long x)
{
    return (sa*x%Mod*x%Mod*x%Mod+sb*x%Mod*x%Mod+sc*x%Mod+sd)%Mod;
}
void gen()
{
    A[0]=0;
    scanf("%lld%lld%lld%lld%lld%lld%lld",&n,&sa,&sb,&sc,&sd,&A[1],&Mod);
    r=max(r,A[1]);
    for(int i=2;i<=n;i++){
        A[i]=(F(A[i-1])+F(A[i-2]))%Mod;
        r=max(r,A[i]);
        //printf("%lld ",A[i]);
    }//printf("\n");
}
long long B[10000050];
bool check(long long x)
{
    //printf("aa%lld\n",x);
    B[0]=0;
    for(int i=1;i<=n;i++){
        if(B[i-1]-A[i]>x)return false;
        if(A[i]>=B[i-1])B[i]=max(B[i-1],A[i]-x);
        else B[i]=min(B[i-1],A[i]+x);
        //printf("%lld ",B[i]);
    }

    return true;
}
int main(){
    gen();
    long long ans=0;
    while(l<=r){
        int mid=(l+r)/2;
        if(check(mid)){
            ans=mid;
            r=mid-1;
        }else l=mid+1;
        //printf("\n");
    }
    printf("%lld\n",ans);
    return 0;
}