#题面
#题目描述
小 Z 是 ZRP(Zombies’ Republic of Poetry,僵尸诗歌共和国)的一名诗歌爱好者,最近他研究起了诗词音律的问题。在过去,诗词是需要编成曲子唱出来的,比如下面这首《菩萨蛮》,唱出来的话其对应 的音符就是这样的:
南 | 园 | 满 | 地 | 堆 | 清 | 絮 | , | 愁 | 闻 | 一 | 霎 | 清 | 明 | 雨 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
因而可以发现,1 1 5 5 6 6 5, 4 4 3 3 2 2 1
这串音符就成为了研究音律的关键。
小 Z 翻阅了众多史料发现,过去的一首曲子的音调是不下降的。小 Z 想要知道对于一首给定的曲子,如何通过提高音调或者降低音调,将它的音调修改得不下降,而且使得修改幅度最大的那个音符的修改幅度尽量小。
即如果把一个包含 个音符的曲子看做是一个正整数数列 ,那么目标是求另一个正整数数列 , 使得对于任意的 有 ,而且使得 尽量小。
小 Z 很快就想清楚了做法,但是鉴于他还忙着写诗,所以这个任务就交给了你。
#输入格式
由于数据规模可能较大,因此采用如下方式生成数据。
每个数据包含六个数:,意为共有 个音符,第一个音符为 。
生成规则如下:定义生成函数 ; 那么给出递推公式 ,此处规定 。
由于中间过程的数可能会特别大,所以要求每一步与 中的每个数都对一个给定的数 取模。
#输出格式
输出一行,包含一个正整数 。
#输入输出样例
样例输入 #1
3 815 6901 3839 178 199 10007
样例输出 #1
1334
样例解释 #1
生成的数列为 ,此时将 修改为 , 也修改为 即可,代价为 。
#数据范围与约定
对于 的数据,,,。
#思路
看到最大值最小,自然而然地就想到了二分答案。
可以从贪心的角度来考虑,每次在满足条件的情况下让 尽可能小更有利于后续处理。
如果 ,则无论如何也无法满足条件,因此该情况不成立。
#代码
1 |
|