每日一题 2.24-3.2
文章目录
上周忙着返校所以没来得及做题，这几天把上周的题目补上。
题目来自 AcWing
6131. 农夫约翰最喜欢的操作 | 原题链接
$M\mid a_i-x$ 对任意 $1\leq i\leq N$ 成立亦可以理解为对任意 $1\leq i,j\leq N$ 有 $a_i\equiv a_j\space(mod\space M)$。使原数列每一个数对 $m$ 取模得到模数列 $b$，再找一个数 $k$ 使得模数列中每一个值与 $k$ 的差的绝对值之和最小，即 $\sum^n_{i=1}|b_i-k|$ 最小，这个最小值就是题目要求的值。看起来这就是 货仓选址 的翻版，只要找到中位数即可。但情况真的如此吗？
实际情况是，由于 $a_i\equiv a_i\pm m\space(mod\space m)$，所有的同余类实际组成了一个环，在这个环上有 $n$ 中不同的取法，也就是说最多可能有 $n$ 个不同的中位数，而题目要求找到这 $n$ 中情况中找到最小的 $\sum^n_{i=1}|b_i-k|$。
如果将每种情况的模数列算出来，再遍历数列求出答案，时间复杂度为 $O(n^2)$ 必然超时。因此使用滑动窗口优化。首先找出最小的模数列，即每一项都小于 $m$，求出这一个模数列的最小 $\sum^n_{i=1}|b_i-k|$，这个值等于$中位数 \times 中位数左侧元素个数 - 中位数左侧元素之和 + 中位数右侧元素之和 - 中位数 \times 中位数右侧元素个数$。当窗口滑动时，中位数右移一位，中位数左右元素数量不变，而左右元素之和只需各自加减对应边界值。这样的时间复杂度为 $O(n)$。
1t = int(input().strip())
2while t > 0:
3 n, m = map(int, input().strip().split())
4 nums = tuple(map(int, input().strip().split()))
5
6 mod = list(map(lambda x: x % m, nums))
7 mod.sort()
8 mid_idx = len(mod) // 2
9 mid = mod[mid_idx]
10 res = 0
11 left_sum = 0
12 right_sum = 0
13 left_count = 0
14 right_count = 0
15
16 for i in range(n):
17 res += abs(mod[i] - mid)
18 if i < mid_idx:
19 left_sum += mod[i]
20 left_count += 1
21 elif i > mid_idx:
22 right_sum += mod[i]
23 right_count += 1
24
25 min_res = res
26 ptr = 0
27
28 for k in range(n - 1):
29 left_sum = left_sum - mod[ptr] + mid
30 mid_idx = (mid_idx + 1) % n
31 mid = mod[mid_idx]
32 mod[ptr] += m
33 right_sum = right_sum - mid + mod[ptr]
34 res = left_count * mid - left_sum + right_sum - right_count * mid
35 if res < min_res:
36 min_res = res
37 ptr += 1
38
39 print(min_res)
40 t -= 1
5437. 拐杖糖盛宴 | 原题链接
本来想先写暴力再优化的，结果暴力就能过。
1n, m = map(int, input().strip().split())
2cows = list(map(int, input().strip().split()))
3candies = list(map(list, zip([0] * m, list(map(int, input().strip().split())))))
4for i in range(m):
5 for j in range(n):
6 if cows[j] >= candies[i][1]:
7 cows[j] += candies[i][1] - candies[i][0]
8 break
9 if cows[j] > candies[i][0]:
10 diff = cows[j] - candies[i][0]
11 cows[j] += diff
12 candies[i][0] += diff
13print(*cows, sep="\n")
这也不难理解。对于每一根糖来说，如果第一头牛把它全部吃掉，那么就会直接进入下一轮循环；如果第一头牛无法把它全部吃掉，那么第一头牛的身高就会翻倍，这样即使在最坏的情况下，也只需要 30 次，第一头牛的身高就会比糖高度的上限还要大，而后面的牛全都无法吃到糖。
5438. 密接牛追踪2 | 原题链接
如果要最开始就被感染的牛数量最少，那么一定是经过的天数尽量多、每头“零号病牛”辐射的病牛尽量多。因此假设最短的一段病牛是同一头牛感染的，此时就可以确定一头牛在有限时间内最多感染这一段数量的牛，所以每一段病牛数量除以最短段病牛数量向上取整就是这一段最初的病牛数量。
对于头尾段的病牛，其感染数量应该翻倍。例如对于 "111101111" 这个序列来说，“零号病牛”最少的情况是队首和队尾的牛在最初感染，此时半径为 7 而非 4。另外如果最短段的病牛数量为偶数，则实际最短段的长度为该段长度减一（奇数确保每头牛感染数量尽量多）。
如果最终有病牛的数量小于等于 2，则说明这是第一天，全部病牛都是最初病牛；如果全部牛都生病，则最初只有 1 头病牛；如果没有牛生病则输出 0。以上情况需要特判。
1from math import ceil
2
3n = int(input().strip())
4cows = list(input().strip())
5segments = list()
6ptr = 0
7for i in range(n):
8 if cows[i] == "0" and cows[ptr] == "1":
9 segments.append(i - ptr)
10 ptr = i
11 if cows[ptr] == "0" and cows[i] == "1":
12 ptr = i
13if cows[-1] == "1":
14 segments.append(n - ptr)
15
16if len(segments) == 0:
17 print(0)
18 exit()
19if len(segments) == 1:
20 print(1)
21 exit()
22
23radius = segments[:]
24if cows[0] == "1":
25 radius[0] *= 2
26if cows[-1] == "1":
27 radius[-1] *= 2
28
29mini = min(radius)
30if mini <= 2:
31 print(sum(segments))
32 exit()
33
34ans = 0
35if mini % 2 == 0:
36 mini -= 1
37for s in segments:
38 ans += ceil(s / mini)
39print(ans)
5439. 农夫约翰真的种地 | 原题链接
这道题实际含义是，给出 $k_1,b_1,k_2,b_2,\cdots k_n,b_n$，求出不等式 $k_1x+b_1>k_2x+b_2>\cdots>k_nx+b_n$ 的最小非负整数解。具体解法是两两解不等式，最终得出解所在的区间。解一定是区间内最小非负整数。如果区间上界小于 0 或者区间上界小于下界，则不等式无解。
1from math import floor, ceil
2
3
4def solve(a_line, b_line):
5 p, k1, b1 = a_line
6 q, k2, b2 = b_line
7 if k1 == k2:
8 if b1 <= b2:
9 return -1
10 else:
11 return 1
12 if k1 > k2:
13 x = floor((b2 - b1) / (k1 - k2)) + 1
14 if x < 0:
15 return 0, 0
16 else:
17 return 0, x
18 else:
19 x = ceil((b2 - b1) / (k1 - k2)) - 1
20 if x < 0:
21 return -1
22 else:
23 return 1, x
24
25
26t = int(input().strip())
27for _ in range(t):
28 n = int(input().strip())
29 init = tuple(map(int, input().strip().split()))
30 delta = tuple(map(int, input().strip().split()))
31 target = tuple(map(int, input().strip().split()))
32 data = sorted(list(zip(target, delta, init)))
33
34 no_solution = False
35 l_bound = 0
36 r_bound = 1e9
37 for i in range(1, n):
38 a_line = data[i - 1]
39 b_line = data[i]
40 res = solve(a_line, b_line)
41 if res == -1:
42 no_solution = True
43 break
44 if res == 1:
45 continue
46 sign, x = res
47 if sign == 0:
48 l_bound = max(l_bound, x)
49 else:
50 r_bound = min(r_bound, x)
51 if no_solution:
52 print(-1)
53 continue
54
55 if l_bound > r_bound:
56 print(-1)
57 continue
58 print(l_bound)
5524. 多数意见 | 原题链接
在原数列中取任意长的一个区间，如果在这一区间内某一个数字出现频率超过 50%，那么这一段数都会变成这一个数。这个操作的有效区间长度至少为 3，而且操作次数无限制。也就是说，在连续的三个数中，如果数字 $n$ 出现了两次及以上，那么这三个数都会变成 $n$，然后 $n$ 会继续向外扩张，直到全部数字都被它同化……
1t = int(input().strip())
2for _ in range(t):
3 n = int(input().strip())
4 nums = list(map(int, input().strip().split()))
5
6 if len(nums) == 1:
7 print(nums[0])
8 continue
9 if len(nums) == 2:
10 if nums[0] == nums[1]:
11 print(nums[0])
12 else:
13 print(-1)
14 continue
15
16 s = set()
17 for i in range(2, n):
18 if nums[i - 2] == nums[i - 1]:
19 s.add(nums[i - 2])
20 elif nums[i - 2] == nums[i]:
21 s.add(nums[i - 2])
22 elif nums[i - 1] == nums[i]:
23 s.add(nums[i - 1])
24
25 if len(s) == 0:
26 print(-1)
27 else:
28 print(*sorted(list(s)))