(贪心)清晰注释 | 数组取精
数组取精
https://www.nowcoder.com/practice/6f77d207b40c41d899d23627d6bd122a
import sys
def main():
input = sys.stdin.readline
# 读取输入
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
# 把每个位置的 (a, b, id) 打包,方便排序和选择
nodes = [[a[i], b[i], i+1] for i in range(n)]
# Step1: 按 a 从大到小排序
# - 确保选择的子集在 A 上容易超过总和的一半
nodes.sort(key=lambda x: x[0], reverse=True)
# Step2: 构造子集
result = []
# 一定要包含第一个元素(a 最大的那个)
result.append(nodes[0][2])
# Step3: 处理成对的元素
# - 每次看两个元素,取 b 更大的那个
# - 这样可以保证在 B 上的和尽量大
for i in range(1, n-1, 2):
if nodes[i][1] >= nodes[i + 1][1]:
result.append(nodes[i][2])
else:
result.append(nodes[i + 1][2])
# Step4: 如果 n 是偶数,多出来的最后一个元素单独加入
if n % 2 == 0:
result.append(nodes[n - 1][2])
# Step5: 输出结果
# - 按升序输出下标(题目要求)
result.sort()
print(len(result))
print(*result)
if __name__ == "__main__":
main()
查看3道真题和解析