A31973. 宝箱
填空题
较难
知识点
题目描述
宝箱
题目描述
小杨发现了n个宝箱，其中第i个宝箱的价值是ai。
小杨可以选择一些宝箱放入背包并带走，但是小杨的背包⽐较特殊，假设小杨选择的宝箱中最大价值为x，最小价值为y ，小杨需要保证 x-y≤k，否则小杨的背包会损坏。
小杨想知道背包不损坏的情况下，自己能够带走宝箱的总价值最大是多少。
输入格式
第一行包含两个正整数n，k，含义如题面所示。
第二行包含n个正整数 a1,a2, , ,an，代表宝箱的价值。
输出格式
输出一个整数，代表带走宝箱的最大总价值。
样例1
输入
5 1
1 2 3 1 2输出
7样例解释
在背包不损坏的情况下，小杨可以拿走两个价值为2的宝箱和一个价值为3的宝箱。
数据范围
对于全部数据，保证有 1≤n≤1000，1≤k≤1000 ，1≤ ai ≤1000
参考答案
N = 1010
a = [0] * N
def main():
n, k = map(int, input().split())
aa = input().split()
for i in range(1, n + 1):
a[i] = int(aa[i-1])
a[1:n + 1] = sorted(a[1:n + 1])
ans = 0
for i in range(1, n + 1):
sum = 0
for j in range(i, 0, -1):
if a[i] - a[j] <= k:
sum += a[j]
else:
break
ans = max(ans, sum)
print(ans)
if __name__ == "__main__":
main()
上一题
下一题