蓝桥杯之贪心与排序

文章目录 训练士兵三国游戏

在蓝桥杯当中，有一类题型就是考察你的思维，在这一类题型中，我们就得使用到这个 贪心+排序的思想在这类题目中，我们就常常会发现，自己会出现，知道大体的思路，但是真正要你进行详细化表达的时候，就发现出现这个思维混乱的情况，对此，我们应该多做一下这类型的题目，多思考细节处理 训练士兵

训练士兵

思路分析：在这一题，我们想的肯定是如果组团的费用便宜的话，我们肯定是使用组团，当然我们还得考虑到什么时候组团不划算(因为你可能会多了一些多余的训练出现)，如何找到这个边界是需要我们进行思考的一个问题！由于考虑到是否多余的问题，所以我们要对输入的元素，按照训练的次数进行降序排序，然后统计找到这个单独训练的时候成本大于一起训练的情况 import os import sys #要么全组团，要么全单独。除非你全单独训练比组团都便宜。 #看看全单独和组团谁便宜。要是组团还贵，以后每次训练都不用组团啦。因为再往后慢慢都顶尖了，费用包减少的。 n,S = map(int,input().split(' ')) pc = [] for i in range(n): p,c = map(int,input().split(' ')) pc.append([p,c]) #pc二维列表，第二维度是每个士兵训练成本和次数 pc.sort(key = lambda x:x[1],reverse = True) #按每个士兵的 ※※训练次数※※ ※※降序排序※※ sump,a,ans = 0,0,0 for i in range(n): sump += pc[i][0] #sump是逐一把左端的p加起来，每次加完都和S比较一下 if sump >= S: a = i - 1 #12~16行是为了找一个下标a，位置a和他前面的p加起来刚好不超过S break ans += pc[a+1][1]*S #a后面的人也要训练，所以为了便宜只能组团。等他们顶尖了就不用组啦~ for i in range(a+1): ans += (pc[i][1]-pc[a+1][1])*pc[i][0] #只剩a及前者时，每人单独练更便宜 print(ans) 三国游戏

思路分析：在本题目中，我们需要考虑三个人的具体情况，因为是比较其中一个人是否大于剩余的两个人，所以将剩余的两个人的情况进行合并处理，然后作差，再进行排序，我们就一直累加，找到当累加结果大于0的最多的发生的事件次数即可 import os import sys # 请在此输入您的代码 n = int(input()) A = list(map(int,input().split())) B = list(map(int,input().split())) C = list(map(int,input().split())) Aw,Bw,Cw = [0]*n,[0]*n,[0]*n for i in range(n): Aw[i] = A[i]-B[i]-C[i] Bw[i] = B[i]-A[i]-C[i] Cw[i] = C[i]-A[i]-B[i] Aw.sort(reverse=True) Bw.sort(reverse=True) Cw.sort(reverse=True) ans = 0 acc = 0 cur = 0 for i in range(n): if acc + Aw[i] >0: acc+=Aw[i] cur+=1 else: break ans = max(cur,ans) acc = 0 cur = 0 for i in range(n): if acc + Bw[i] >0: acc+=Bw[i] cur+=1 else: break ans = max(cur,ans) acc = 0 cur = 0 for i in range(n): if acc + Cw[i] >0: acc+=Cw[i] cur+=1 else: break ans = max(cur,ans) if ans !=0: print(ans) else: print(-1)