题目描述
小 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 很快就想清楚了做法,但是鉴于他还忙着写诗,所以这个任务就交给了你。
输入描述
由于数据规模可能较大,因此采用如下方式生成数据。
每个数据包含6个数:n,Sa,Sb,Sc,Sd,A[1],Mod,意为共有 n 个音符,第一个音符为 A[1]
生成规则如下:
定义生成函数F(x) = Sa*x^3 + Sb*x^2 + Sc*x + Sd; 那么给出递推公式A[i] = F(A[i-1]) + F(A[i-2]),此处规定A[0]=0.
由于中间过程的数可能会特别大,所以要求每一步与A中的每个数都对一个给定的数 Mod 取模。
输出描述
输出一行,包含一个正整数 Ans。
示例1
输入
3 815 6901 3839 178 199 10007
输出
1334
备注
对于 \(10\%\) 的数据, \(n \le 3\)
对于 \(20\%\) 的数据, \(n \le 10\)
对于 \(30\%\) 的数据, \(n \le 100\)
对于 \(50\%\) 的数据, \(n \le 1000\)
对于 \(70\%\) 的数据, \(n \le 100000\)
对于 \(100\%\) 的数据, \(n \le 5000000,S_a,S_b,S_c,S_d,A[1] \le 10000,Mod \le 1000000007\)
知识点:二分。
很显然二分答案,二分一个阈值范围。
注意到需要不减,那么前一个点高度越低越好,给后面的点留足高度。
那么第一个节点直接到最低 \(A[1] - mid\),后面第 \(i\) 个节点如果 \(A[i] < A[i-1]\) ,则把 \(A[i]\) 提升到与 \(A[i-1]\) 相等为了最低限度满足条件 ,如果最后还是 \(A[i] + mid < A[i-1]\) 说明不可行,否则通过;如果 \(A[i] \geq A[i-1]\) ,则把 \(A[i]\) 降低到与 \(A[i-1]\) 相等为了给后面留空间,但可能降低不到,所以 \(A[i] = max(A[i]-mid,A[i-1])\) 。
最后如果循环结束没有跳出,就是可行方案。
为了不修改 \(A[i]\) ,用 \(pre\) 保存上一个点数据。
时间复杂度 \(O(n \log Mod)\)
空间复杂度 \(O(n)\)
#include <bits/stdc++.h>
using namespace std;
int n, a[5000007], s[4], mod;
int f(int x) {
return (1LL * s[0] * x % mod * x % mod * x % mod +
1LL * s[1] * x % mod * x % mod +
1LL * s[2] * x % mod +
s[3]) % mod;
}
bool check(int mid) {
int pre = 1 << 31;
for (int i = 1;i <= n;i++) {
if (a[i] >= pre) pre = max(pre, a[i] - mid);
else if (a[i] + mid < pre) return 0;
}
return 1;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> s[0] >> s[1] >> s[2] >> s[3] >> a[1] >> mod;
for (int i = 2;i <= n;i++)
a[i] = (f(a[i - 1]) + f(a[i - 2])) % mod;
int l = 0, r = mod;
while (l <= r) {
int mid = l + r >> 1;
if (check(mid)) r = mid - 1;
else l = mid + 1;
}
cout << l << '\n';
return 0;
}
手机扫一扫
移动阅读更方便
你可能感兴趣的文章