P8872 [传智杯 #5 初赛] D-莲子的物理热力学

题目链接：P8872 [传智杯 #5 初赛] D-莲子的物理热力学 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

参考了题解，自己在这再写一遍

假设数组有序且经过m次操作后的数组最小值为l，最大值为r，u代表所有严格小于l的值的个数，v代表所有严格大于r的个数，原数组经过m次操作的过程为：1.u<v，将u个数全部变为最大值，此时最小值为l，再将u+l个数全部变为最小值l 2.u>v，将v个数全部变为最小值，此时最大值为r，再将u+v个数全部变为最大值r 3.u=v ，可代入前两种的任一一种，将其归为 u+v+min(u,v) 且u+v+min(u,v) = m

令第一个值为l的下标为i(数组下标从0开始)，则 j 的取值一共有两种可能:(1) u<v , j = m - 2*u (2) u>v, j = (m - u) // 2 (1),(2)两种情况，哪个更大，j 取哪个

注意: 1.m可能大于n-1(下标从0开始，当 i = n - 1 ，代表有n-1个数需要改变)，因此在m，n中需要比较取最小值 2.判断循环退出条件时，i为最小值l的下标，并不是统计小于l的个数u，因此退出条件应为 i <= min(n-1,m) 3. j = m - 2*u 的下标可能为负值，需要排除

Python代码如下：

n,m = map(int,input().split())

A = list(map(int,input().strip().split()))

A.sort()

Min = min(n-1,m)

Max = A[-1] - A[0]

i = 0

while i <= Min:

    j = (Min - i)//2

    k = Min - 2 * i

    if j > k:

        if A[n-j-1] - A[i] < Max:

            Max = A[n-1-j] - A[i]

    elif k>= 0 and A[n-1-k] - A[i] < Max:

        Max = A[n-1-k] - A[i]

    i += 1

print(Max)

巴特西

P8872 [传智杯 #5 初赛] D-莲子的物理热力学

最新文章

热门文章