求助第二题的写法错在哪里?
#拼多多集团-PDD笔试#
已知有K个位置,N个偶像,后续会读取K个坐标,求将这N个偶像分散排布,最终偶像之间最短的距离是多少?
我认为这道题目就是从K个位置选N,就用贪心法每次扫描删去一个位置,知道最后结果等于N,三道给出的已知样例全部正确,但是结果是0%😱
```
T = int(input())
for _ in range(T):
K, N = map(int, input().split())
k_list = list(map(int, input().split()))
k_list.sort() # 对位置进行排序
cnt = K - N # 合并次数
for _ in range(cnt):
ml = 0 # 待合并的左
min_sum = k_list[ml + 2] - k_list[ml]
for i in range(len(k_list) - 2):
if k_list[i+2] - k_list[i] < min_sum:
ml, min_sum = i, k_list[i+2] - k_list[i]
del k_list[ml+1]
print(min(k_list[i+1] - k_list[i] for i in range(len(k_list) - 1)))
```
已知有K个位置,N个偶像,后续会读取K个坐标,求将这N个偶像分散排布,最终偶像之间最短的距离是多少?
我认为这道题目就是从K个位置选N,就用贪心法每次扫描删去一个位置,知道最后结果等于N,三道给出的已知样例全部正确,但是结果是0%😱
```
T = int(input())
for _ in range(T):
K, N = map(int, input().split())
k_list = list(map(int, input().split()))
k_list.sort() # 对位置进行排序
cnt = K - N # 合并次数
for _ in range(cnt):
ml = 0 # 待合并的左
min_sum = k_list[ml + 2] - k_list[ml]
for i in range(len(k_list) - 2):
if k_list[i+2] - k_list[i] < min_sum:
ml, min_sum = i, k_list[i+2] - k_list[i]
del k_list[ml+1]
print(min(k_list[i+1] - k_list[i] for i in range(len(k_list) - 1)))
```
全部评论
leetcode 1552、两球之间的磁力
最小值最大化 用二分法
我知道了,这是ACM的变种题,愤怒的牛,问Deep Seek回答不对,Gemini给出了反例:假设 $K = 5$, $N = 3$,坐标数组为 [0, 10, 12, 14, 24]。还得是洋人的AI。
我也这么做的,问AI说是局部最优推不出全局最优。
用二分答案,check 函数贪心每次选距离上一个大于等于k的最小坐标
二分枚举
相关推荐