M18211: 军备竞赛

greedy, two pointers, http://cs101.openjudge.cn/pctbook/M18211

鸣人是木叶村的村长，最近在跟敌国进行军备竞赛，他手边有N份武器设计图，每张设计图有制作成本（大于等于零）且最多使用一次，可以选择花钱制作或是以同样的价钱卖给敌国，同时任意时刻敌国的武器不能比我国更多，鸣人的目标是在不负债的前提下武器种类比敌国越多越好。

输入

第一行为起始整数经费p,并且0≤p。且要求任何时刻p不能小于0. 第二行为n个整数，以空格分隔，并且0≤每个整数。代表每张设计图的制作成本，同时也是卖价，最多用一次(无法又制作又卖).

输出

一个整数，代表武器种类最多比敌国多多少.

样例输入

Sample1 Input:
10
20 30 40

Sample1 Output:
0

解释: 10元不足以制作20元的武器，所以为0，也不能先卖50元的，不能让敌国武器比木叶多

Sample2 Input:
10
15 5

Sample2 Output:
1

解释: 10元可以制作5元的武器，木叶的武器比对手多一件

样例输出

Sample3 Input:
40
20 80 60 40

Sample3 Output:
2

解释: 先制作20元的武器，再贩卖80元的武器，这时经费为100，再制作40、60的武器，木叶的武器比对手多二件

来源：cs101-2018

典型的“双指针 + 贪心”写法，可以在买卖武器（或能量换分数）问题中高效求出最大收益。

python

from collections import deque

money = int(input())
weapons = deque(sorted(map(int, input().split())))
score = 0
best = 0

while weapons and (money >= weapons[0] or score):
    if money >= weapons[0]:         # 买最便宜的
        money -= weapons.popleft()
        score += 1
        best = max(best, score)     # 记录最高分
    else:                           # 卖最贵的
        money += weapons.pop()
        score -= 1

print(best)

python

# 22 信科 吴明睿
# 读取输入
p = int(input())
cost = sorted(list(map(int, input().split())))

# 初始化变量
i, j, cnt = 0, len(cost) - 1, 0

# 使用双指针方法处理成本列表
while i < j:
    if cost[i] <= p:
        # 如果当前最小成本小于或等于剩余金额，则购买并更新相关变量
        cnt += 1
        p -= cost[i]
        i += 1
    elif cnt:
        # 如果剩余金额不足以支付当前最小成本且已购数量不为零，则回退最后一个购买项
        cnt -= 1
        p += cost[j]
        j -= 1
    else:
        # 如果无法再进行任何操作则退出循环
        break

# 输出最终能够购买的数量
print(cnt + (cost[i] <= p))

python

# 24n2400011491 王思杰
from collections import deque

# 读取输入
p = int(input())
w = list(map(int, input().split()))
w.sort()

# 将列表转换为 deque
w = deque(w)

a = 0  # 记录购买的物品数量
b = 0  # 记录退回的物品数量

while len(w) > 0:
    while p > 0 and len(w) > 0:
        if p >= w[0]:
            p -= w.popleft()  # 从左侧移除并更新剩余金额
            a += 1
        else:
            break

    if len(w) <= 1:  # 如果只剩下一个或没有物品，则退出循环
        break

    if a > b:
        p += w.pop()  # 从右侧移除并增加剩余金额
        b += 1
    else:
        break

print(a - b)

思路：把武器价格从小到大排序，然后用二分双指针left, right技巧，有钱就买（制作），没钱就卖。感谢2020fall-cs101 汤建浩，指正 cnt<0情况。

python

p = int(input())
n = [int(x) for x in input().split()]
n.sort()

cnt = 0
left = 0
right = len(n) - 1

while left<=right:
    if n[left]<=p:
        cnt += 1
        p -= n[left]
        left += 1
    else:
        if right==left:
            break
        
        p += n[right]
        cnt -= 1
        if cnt<0:
            cnt=0
            break

        right -= 1

print(cnt)

M18211: 军备竞赛 ​

M18211: 军备竞赛