拼多多算法工程师第二批：珍珠一题

我搞了好多测试样例都通过了，就是在上面通不过0%.我哭了

滑动窗口+维护队列例子: 1000 4 1 4 995 998先把环变成序列1 4 995 998 1001 1004 1995 1998然后维护队列left,right对于滑动窗口 1 4 995 998left = 1,4 right=995,998 对于滑动窗口 4 995 998 1001left = 4,995 right=998,1001 对于滑动窗口 995 998 1001 1004left = 995,998 right=1001,1004 对于滑动窗口 998 1001 1004 1995left = 998,1001 right=1004,1995 维护left和right队列的和就可以计算出结果

我觉得是不是可以转项链，依次把0位置转到每个珍珠，然后这个珍珠作为最终结果最左侧的珍珠，然后就是算所有非负数往中位数靠的最小距离了，应该复杂度是O(k^2)

受到杨超度同学思路的启发，我觉得这道题可以这样想，需要一个先验知识：X轴上有N个点，求X轴上一点使它到这N个点的距离之和最小。那么根据中位数性质，这个点一定是这组数中的中位数（该性质的简单证明可以参考https://blog.csdn.net/sm_545/article/details/78196351）。 这道题在先验知识的基础上有两个变形，首先题目要求是环，那么我们就在这N个数后面再补上N个数（其中新加的N个数分别是前N个数加环的长度L）然后我们从中截取N段，使得每段都包含了所有的数，分别对每段应用先验知识；其次题目要求移动到相邻位置，那就在先验知识的基础上减去一个常数即可。因为一旦N给定，这个常数就确定了（具体求法见下方代码） public static void main(String[] args){     Scanner sc = new Scanner(System.in);     int result = Integer.MAX_VALUE;     int L = sc.nextInt();  //项链的长度     int N = sc.nextInt();  //珍珠的个数     int[] nums = new int[2*N+1];  //存拓展后的珍珠位置编号     int m, constant = 0;     m = (N+1) / 2;     for(int i = 1; i <= N ; i++){         nums[i] = sc.nextInt();         constant += Math.abs(m - i);  //求先验知识和本题差的那个常数     }     Arrays.sort(nums, 1, N+1);  //排序前N个数     for(int i = N+1; i <=2*N; i++) {         nums[i] = nums[i - N] + L;  //拓展，补上N个数     }     for(int left = 1; left <= N; left++){  //截取N段，每段包含了所有的珍珠         int answer = 0;  //按照先验知识求的距离和         int right = left + N-1;         int i = left, j = right;         while(i <= j){             answer += nums[j--] - nums[i++];         }         result = Math.min(answer - constant, result);     }     System.out.println(result); }

思路间代码注释 def minDistance():     '''     想法:         如果项链是一条线,不是环,那么线上各珍珠最小移动距离为到中位数的移动距离,         所以遍历项链的n个位置,剪断,将项链拉成一条线,此时求最短移动距离,然后取最短     '''     l,n=list(map(int,input().strip().split()))     pos=list(map(int,input().strip().split()))     def __mindistance(onepos):         '''每条线的最短移动距离'''         if n%2==0 and n>2:             midNum1=onepos[n//2]             midNum2 = onepos[n//2 -1]             steps1 = 0             steps2 = 0             for num in onepos:                 steps1 += abs(num - midNum1)                 steps2 += abs(num - midNum2)             pianyi = 0             for i in range(n//2 -1):                 pianyi += i             steps = min(steps1, steps2)             return steps - pianyi * 2 - n         else:             zhongweishu = onepos[n // 2]             steps = 0             for num in onepos:                 steps += abs(num - zhongweishu)             pianyi = 0             for i in range(n // 2):                 pianyi += i             return steps - pianyi * 2 - n+1     minstep=sum(pos)     for i in range(l):         pos_temp=[po-i if po>=i else l-i+po for po in pos]         pos_temp.sort()         step=__mindistance(pos_temp)         if step<minstep:             minstep=step     return minstep

要么都向0移动，要么这些点求个坐标均值，向均值左右点移动，for一遍就好了

列举所有窗口大小为N的连续子串，排序后与原始珍珠位置排序后对位想减，求和，返回最小的

我有点思路，写不来呀

数组倍增，然后记录坐标前缀和，之后滑动窗口统计？

码了，同问

同问

有没有对应的题可以再做一遍...

我写好了，就是本地测试了，后面贴上去没见到结果就交卷了。 思路是，指定要往数组中的哪个数靠拢O(n)，固定好之后，设置两个指针，用贪心法，算往这个数靠拢的需要步数和，总共需要O(n^2）估计会超时

求 放珍珠的区间坐标和和原始坐标和的差的绝对值

1、对于大于500的编号998和995，作为减数与1000相减，得到2和5 2、以编号为0的珍珠作为参考点，计算四个珍珠到0号珍珠的距离，例：编号为1的珍珠到0号的距离为1-0-1=0，编号为4的珍珠到0号的距离为4-0-1=3，编号为998的珍珠到0号的距离为2-0-1 =1，编号为995的珍珠到0号的距离为5-0-1=4 3、距离相加为0+3+1+4=8 （也可表示为1+4+（1000-998）+（1000-995）-4=8）

有思路写了半天也没办法AC。。我是每次赋值的时候比较一下减不减去总个数的绝对值，按小的取模，998和995就变成-2和-5了

以500为界限，将珍珠集合到0到500的坐标上，求出中心点，在讨论

模一下总长向0移动。。但我还是做不对，哭哭

# 不知道能不能过，求题目测试 # 这种做法的时间复杂度应该是O(klgk+kn) import sys def calc_movement(start, end):     global total_num     global position     movement = 0     if end >= total_num:         position.append(total_num + position[0])         position.pop(0)     for idx, num in enumerate(position):         movement += abs(start + idx - num)     return movement if __name__ == "__main__":     line1 = sys.stdin.readline().strip().split()     line2 = sys.stdin.readline().strip().split()     line1 = map(int, line1)     line2 = map(int, line2)     total_num = line1[0]     position = line2     position = sorted(position)     window_size = len(position)     result = sys.maxint     for i in range(total_num):         result = min(result, calc_movement(i, i + window_size-1))     print result

每次更新一对起点和终点，然后计算移动次数； 比如1 2 995 998，先拿1~998，计算都往1~998的某个区间移动步数， 然后把998变为-2，计算-2~995的区间移动步数， 每次计算移动步数时间为O(n)，一共更新比较n次，然后就O(n^2)