Loading... ## 前言 挺有意思的题,记录一下。 ## 正文 ### 分析题目 简化一下题意,有一个无限长的的数组,从负无穷到正无穷,然后初始这个数组上一些点有一些数,现在可以使用两种操作让这个数组任意两个相邻的数的和不超过一,首选选择一个下标 $p$: 1. 让 $a_p$ 加一,$a_{p-1},a_{p-2}$ 减一。 2. 让 $a_p$ 减一,$a_{p-1},a_{p-2}$ 加一。 首先这两个操作是互逆的。然后这个操作会给人一种感觉,就是 $p-1,p-2$ 位置上的数各取一,和一个 $p$ 位置取一是等价的。所以可以花费 $p-1,p-2$ 位置各减去一作为代价,让 $p$ 位置加上一,另一个操作同理。 那就给每个位置钦定一个权值 $w_p$ 可以满足这样的条件,肯定有 $w_p=w_{p-1}+w_{p-2}$,即斐波那契数列。这样每次操作后数组的带权和不变,我们令这个值是 $s$,那么结束状态就是把 $s$ 拆分成不同且不相邻的一些斐波那契数之和,所以把问题转化为求一个数的斐波那契拆解(我也不知道这个叫什么)。 求解方法很简单,每次减去小于等于这个数的最大斐波那契数即可。为什么这样是对的呢,用归纳法证明,首先 $s$ 是一或者二可以直接拆解,那么设当前已知分解方法的最大的数是 $n$,现在来分解 $n+1$,找到的小于等于 $n+1$ 的最大斐波那契数是 $f$,那么 $n+1-f\leq n$ 所以一定能拆解下去。那么可不可能分解出来有相邻的数呢?不可能,假设分解出 $fib_{i-1}$ 和 $fib_i$,再找最大的斐波那契数的时候就会找 $fib_{i+1}$ 了,而不是这两个。 ### 代码实现 由于需要高精,建议使用 python 实现,并且钦定权值要从小一点的地方开始钦定,这里建议是 $-100$。 ```python B=100 n=int(input()) pos=[0]*100010 val=[0]*100010 fib=[0]*200010 fib[0]=fib[1]=1 res=[] sumFib=0 cnt=0 minp=0x3f3f3f3f maxp=0 for i in range(0,n): [pos[i],val[i]]=map(int,input().split()) maxp=max(pos[i],maxp) minp=max(pos[i],minp) cnt=maxp+B for i in range(2,cnt+1): fib[i]=fib[i-1]+fib[i-2] for i in range(0,n): sumFib+=fib[pos[i]+B]*val[i] while fib[cnt]<sumFib: fib[cnt+1]=fib[cnt]+fib[cnt-1] cnt+=1 while sumFib>0: while fib[cnt]>sumFib: cnt-=1 res.append(cnt-B) sumFib-=fib[cnt] res.reverse() print(*res) ``` 最后修改:2024 年 04 月 02 日 © 允许规范转载 打赏 赞赏作者 赞 如果觉得我的文章对你有用,请随意赞赏