【每日一题】南园满地堆轻絮 题解

Description

小 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 很快就想清楚了做法，但是鉴于他还忙着写诗， 所以这个任务就交给了你。

Solution

坑点：数据是 ，题目里面没有说，注意取模
思路：二分答案
首先构造出数组A，随后，每次二分答案 的时候，对于第一个点，显然可以先减去 。对于后续的 , 如果比前面大，那么可以变成
如果比前面小，那么可以变成 , 此时判断是否满足 即可。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
const int N = 5e6 + 5;
ll a[N], b[N];
ll Sa, Sb, Sc, Sd, Mod;
int n;
bool check(ll x) {
  for(int i = 1; i <= n; i++) {
    b[i] = a[i];
  }
  b[1] -= x;
  for(int i = 2; i <= n; i++) {
    if(b[i] < b[i - 1]) {
      ll tmp = abs(b[i - 1] - b[i]);
      if(tmp > x) {
        return false;
      }
      b[i] = max(b[i - 1], b[i] - x);
    } else {
      b[i] = max(b[i - 1], b[i] - x);
    }
  }
  return true;
}
ll cal(ll i) {
  ll res = (Sa * (((i * i) % Mod * i) % Mod)) % Mod;
  res += (Sb * ((i * i) % Mod)) % Mod;
  res += ((Sc * i) % Mod + Sd) % Mod;
  res %= Mod;
  return res;
}
int main() {
  FAST_IO;
  cin >> n >> Sa >> Sb >> Sc >> Sd >> a[1] >> Mod;
  for(int i = 2; i <= n; i++) {
    a[i] = cal(a[i - 1]) + cal(a[i - 2]);
    a[i] %= Mod;
  }
  ll left = 0, right = 2e9;
  ll ans = 0;
  while(left <= right) {
    ll mid = left + right >> 1;
    if(check(mid)) {
      ans = mid;
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
  cout << ans << "\n";
  return 0;
}