蓝桥杯 之 贪心与排序

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

训练士兵

训练士兵

• 思路分析：在这一题，我们想的肯定是如果组团的费用便宜的话，我们肯定是使用组团，当然我们还得考虑到什么时候组团不划算(因为你可能会多了一些多余的训练出现)，如何找到这个边界是需要我们进行思考的一个问题！
• 由于考虑到是否多余的问题，所以我们要对输入的元素，按照训练的次数进行降序排序，然后统计找到这个单独训练的时候成本大于一起训练的情况

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)