贪心策略练习

2025-02-15 · 5 分钟阅读 · 算法贪心策略 ·

复制链接:

文章目录

题目来自 AcWing

贪心更像是一种策略和思想，而不是某一种特定的算法。

1055. 股票买卖 II | 原题链接

这道题的解决思路就是的低价卖高价卖。因为可以买卖多次，因此通过追求局部最优解得到答案。

1n = int(input())
2nums = tuple(map(int, input().split(" ")))
3
4profit = 0
5for i in range(1, n):
6    if nums[i] > nums[i - 1]:
7        profit += nums[i] - nums[i - 1]
8
9print(profit)

104. 货仓选址 | 原题链接

货仓的在数轴上的位置一定在最小值和最大值之间，以确保总距离最近。当只有两个商店时，只要货仓的位置在两个商店中间，则总距离一定最小且相等；如果再增加两个商店，当货仓的位置位于所有商店的中间时，总距离依然最小且相等……再假设商店 $A_1,A_2,\cdots A_n$ 的位置升序排列，则货仓的位置一定在编号最中间的商店。

 1n = int(input())
 2nums = list(map(int, input().strip().split(" ")))
 3
 4if n == 1:
 5    print(0)
 6    exit()
 7
 8if n == 2:
 9    print(abs(nums[1] - nums[0]))
10    exit()
11
12nums.sort()
13pos = -1
14if n % 2 == 0:
15    pos = (nums[n // 2] + nums[n // 2 - 1]) // 2
16else:
17    pos = nums[n // 2]
18
19distance = 0
20for i in nums:
21    distance += abs(i - pos)
22
23print(distance)

112. 雷达设备 | 原题链接

首先以小岛为圆心，在岸上画出可以监测到小岛的区间。此时题目转换成在数轴上给出 n 个区间，最少点多少个点能够使每个区间中至少有一个点。

以每个区间的右端点为 key 排序，然后选定第一个区间的右端点，依次检测每个区间的左端点是否在这个点的左侧。如果是则说明这两个区间可以共享一个点，否则则以新的一个区间的右端点作为基准点继续检测。

 1n, d = map(int, input().strip().split(" "))
 2islands = list()
 3for _ in range(n):
 4    x, y = map(int, input().strip().split(" "))
 5    if y > d:
 6        print(-1)
 7        exit()
 8    r = (d**2 - y**2) ** 0.5
 9    islands.append((x - r, x + r))
10
11islands.sort(key=lambda x: x[1])
12count = 1
13current = islands[0]
14for i in range(n):
15    if islands[i][0] > current[1]:
16        count += 1
17        current = islands[i]
18print(count)

1235. 付账问题 | 原题链接

当标标准差尽可能小的时候，每个人付的钱都应该尽量贴近平均值。如果有人带的钱少于平均值，那么就让他把自己带的钱都花掉，然后剩下的人继续平摊。一直重复这个过程即可标准差最小。

 1n, s = map(int, input().strip().split(" "))
 2a = list(map(int, input().strip().split(" ")))
 3mean = s / n
 4
 5
 6def std_dev(data, avg):
 7    if len(data) == 0:
 8        return 0.0000
 9    sq_diff = [(x - avg) ** 2 for x in data]
10    var = sum(sq_diff) / len(data)
11    res = var**0.5
12    return res
13
14
15a.sort()
16paid = list()
17
18while n > 0:
19    avg = s / n
20    current = list(filter(lambda x: x <= avg, a[-n:]))
21    if len(current) == 0:
22        paid.extend([avg] * n)
23        s -= sum(a[-n:])
24        n = 0
25    else:
26        paid.extend(current)
27        s -= sum(current)
28        n -= len(current)
29
30result = std_dev(paid, mean)
31print(f"{result:.4f}")

这段代码是正确的但是没有 AC，又是浮点数存储格式的问题。输出 292984721.9100；标准答案 292984721.9099。

2.18 更新：看到 7 天前提交的工单已处理就又试了试，现在这段代码可以 AC。

1239. 乘积最大 | 原题链接

首先，深搜是绝对会超时的。

做以下几个特判：

当 k == n 时，全部数字都要选。
当 k == 1 时，选最大数。
当 nums 全部为负数时，将最大的 k 个数相乘。

完成上面这些特判之后，对 k 分情况讨论：

当 k % 2 == 0 时，res 一定为正。从大到小选出偶数个正数，从小到大选出偶数个负数（即绝对值最大）相乘。
当 k % 2 != 0 时，先选出最大的最大的一个值，随后将剩下的值按照 k % 2 == 0 的情况处理。

选数的时候，选择最大两个数乘积和最小两个数乘积中更大的那个，以确保每次添加的乘积都是正数。

 1MOD = 1000000009
 2
 3
 4def mod(x):
 5    return x % MOD if x >= 0 else -(-x % MOD)
 6
 7
 8max_value = float("inf")
 9all_negative = True
10
11n, k = map(int, input().strip().split(" "))
12nums = list()
13for _ in range(n):
14    nums.append(int(input().strip()))
15    if nums[-1] >= 0:
16        all_negative = False
17    if nums[-1] > max_value:
18        max_value = nums[-1]
19
20if k == 1:
21    print(mod(max_value))
22    exit()
23
24if k == n:
25    res = 1
26    for i in nums:
27        res *= i
28    print(mod(res))
29    exit()
30
31nums.sort()
32if all_negative and k % 2:
33    res = 1
34    for i in range(k):
35        res *= nums[n - i - 1]
36    print(mod(res))
37    exit()
38
39
40lptr = 0
41rptr = n - 1
42res = 1
43if k % 2:
44    res *= nums[rptr]
45    rptr -= 1
46    k -= 1
47while k:
48    lv = nums[lptr] * nums[lptr + 1]
49    rv = nums[rptr] * nums[rptr - 1]
50    if lv > rv:
51        res *= lv
52        lptr += 2
53    else:
54        res *= rv
55        rptr -= 2
56    k -= 2
57
58print(mod(res))

1247. 后缀表达式 | 原题链接

这道题的关键点在于后缀表达式。因为题目使用后缀表达式，结果就不是简单让最大的 n + 1 个数的和减去最小的 m 个数的和。例如使用 -1 -2 -3 4 + - - 能组成的结果最大的后缀表达式是 4 -3 -2 + - -1 -，转化为中缀表达式为 4-(-3+(-2))-1=10，而非 4+(-3)-(-2)-(-1)=4。因为使用后缀表达式，我们可以将其转化为 $a_1+a_2+\cdots-(a_k+a_{k+1}-a_{k+2}-\cdots)$。当减号的数量不为 0 时，我们可以通过将减号放进括号里来实现加法，将加号放进括号里来实现减法。通过此方法，当减号的数量不为 0 时，实际上可用的减号数量为 [1, m + n]。

 1n, m = map(int, input().strip().split(" "))
 2nums = list(map(int, input().strip().split(" ")))
 3
 4if m == 0:
 5    print(sum(nums))
 6    exit()
 7
 8nums.sort()
 9
10if nums[0] >= 0:
11    print(sum(nums[1:]) - nums[0])
12    exit()
13
14if nums[0] < 0 and nums[-1] >= 0:
15    print(sum(map(abs, nums)))
16    exit()
17
18if nums[-1] < 0:
19    print(nums[-1] - sum(nums[:-1]))

1248. 灵能传输 | 原题链接

好难的题 QAQ

这道题的第一步是计算这一个数列的前缀和。令前缀和序列为 $s$，则当一次灵能传输在位置 $i$ 发生时，有 $a'{i-1}=a{i-1}+a{i},\space a'i=-a_i,\space a'{i+1}=a_i+a_{i+1}$，对于前缀和 $s$ 来讲则有 $s'{i-1}=s{i-1}+a_i=s_i,\space s'i=s'{i-1}+a'i=s{i-1},\space s'{i+1}=s'i+a'{i+1}=s{i+1}$。观察可发现，进行一次灵能传输实际上是交换前缀和数列中两个元素的位置。而题目要求的 $max^n_{i=1}|a_i|$ 可以表示为 $max^n_{i=1}|s_i-s_{i-1}|$。所以题目的实际意思是对 $s$ 做排序，使这种排序中 $max^n_{i=1}|s_i-s_{i-1}|$ 的值最小。

然而坑就在这个地方。因为对数列 $a$ 的首尾元素直接做灵能传输操作为非法，所以 $s$ 中的首尾元素的位置是无法改变的。因此需要寻找的排序方法要在首尾元素不变的情况下满足要求。这个过程在这篇题解中有详细解释。

 1INF = float("inf")
 2
 3t = int(input().strip())
 4
 5
 6def check(s, n):
 7    if s[0] > s[-1]:
 8        s[0], s[-1] = s[-1], s[0]
 9    front = s[0]
10    rear = s[-1]
11    s.sort()
12    front_index = s.index(front)
13    rear_index = s.index(rear)
14
15    sorted_s = [0] * n
16    sorted_s[0] = front
17    sorted_s[-1] = rear
18
19    lptr = 1
20    for i in range(front_index - 2, -1, -2):
21        sorted_s[lptr] = s[i]
22        s[i] = INF
23        lptr += 1
24
25    rptr = n - 2
26    for i in range(rear_index + 2, n, 2):
27        sorted_s[rptr] = s[i]
28        s[i] = INF
29        rptr -= 1
30
31    for i in range(n):
32        if s[i] != INF and i != front_index and i != rear_index:
33            sorted_s[lptr] = s[i]
34            lptr += 1
35
36    max_diff = 0
37    for i in range(n - 1):
38        max_diff = max(max_diff, abs(sorted_s[i] - sorted_s[i + 1]))
39
40    return max_diff
41
42
43for _ in range(t):
44    n = int(input().strip())
45    a = tuple(map(int, input().strip().split(" ")))
46    s = [0]
47    for i in range(n):
48        s.append(a[i] + s[i])
49    print(check(s, n + 1))