南园满地堆轻絮

题意看了好久才明白(:з」∠)
给一个序列a[],要求一个不会递减的数组b[]，并且b要满足|a[i]-b[i]|尽量小

用二分找a与b的差值
如果差值是x
如果a[i]>=b[i-1],那b[i]=max(b[i-1],a[i]-x)
如果a[i]<b[i-1]-x,那差值x就不成立
其他情况就可以让b[i]=b[i-1]

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <stack>
#include <queue>
#include <cmath>
#define ll long long
#define pi 3.1415927
#define inf 0x3f3f3f3f
using namespace std;
ll n,m,sa,sb,sc,sd,mod,a[5000005],b;
ll fun(ll x)
{
    ll a=(sa*x%mod)*x%mod *x%mod,b=sb*x%mod*x%mod,c=sc*x%mod,d=sd%mod;
    return ((((a+b)%mod)+c)%mod+d)%mod;
}
int check(int x)
{
    b=a[1]-x;
    for(int i=2;i<=n;++i)
        if(a[i]>=b)
            b=max(b,a[i]-x);
        else if(a[i]<b-x)
            return 0;
    return 1;
}
int main ()
{
    ll T,i,t,j,k,p,sum=0;
    cin>>n>>sa>>sb>>sc>>sd>>a[1]>>mod;
    for(i=2;i<=n;++i)
        a[i]=(fun(a[i-1])+fun(a[i-2]))%mod;
    ll l=0,r=inf,ans=-1;
    while(l<=r){
        ll mid=(l+r)/2;
        if(check(mid))
            r=mid-1,ans=mid;
        else l=mid+1;
    }
    cout<<ans<<endl;
    return 0;
}