谨用来记录自己的解发
查看原帖
谨用来记录自己的解发
518110
OJone楼主2024/10/17 14:51
我们来分析下规律,
n个元素,进行n次操作,每一次的操作范围是

[1],	[1,2],	[1,2,3],	[1,2,3,4]... [1,2,3,4...n]

第1个元素操作 n  次
第2个元素操作 n-1次
第3个元素操作 n-2次
...
第i个元素操作 n-(i-1)次

然后根据题目意思,每次操作分两个小操作,①是移动位置,②是取反。

那取反好办了,操作次数是偶数次的不变,奇数次的变一次【思考下,能否说服自己】

第i个元素的移动位置怎么移的呢,在具体到数列中看看
	【1234】
	
①  【1, 2, 3, 4】
②  【2, 1, 3, 4】
③  【3, 1, 2, 4】
④  【4, 2, 1, 3】

①号 共移动 n-(1-1) 次, 4次, 第1次 移动了 0位,第2次右移了 1位, 第3次移动了0位, 第4次右移了1位
②号 共移动 n-(2-1) 次, 3次,  第1次 左移了 1位,第2次右移了 2位, 第3次左移了1位
③号 共移动 n-(3-1) 次, 2次,  第1次 左移了 2位, 第2次右移了 3位

即 第i号元素 第1次左移 i-1位,第2次右移i位,第3次左移i-1位

那我们知道 了 移动次数 后 是不是可以直接算出 每个元素最终的位置呢?

假设是移动次数是 n,
	n是偶数的话, 第i个元素 移动的位置即 i -(n/2)*(i-1) + (n/2)*(i);
	n是奇数的话, 第i个元素 移动的位置即 i +(n/2)*(i) - (n-n/2)*(i-1);

至此,问题全部解决了
2024/10/17 14:51
加载中...