今日复习内容：算法双周赛
第一题：疯狂星期六
题目描述：
麦肯鸡是一家名声在外的汉堡店，他们最近推出了一份名为vivo50的套餐，只需要在门口大声喊出vivo50，就可以获得这个套餐。
现在，请你打印出vivo50，告诉计算机你想要这个套餐，虽然计算机无法为你提供这个套餐，但它可以帮助你通过本题。
输入格式：
本题为填空题，无需输入即可作答。
输出格式：
输出一个字符串，表示答案。
参考答案：
print("vivo50")这个结果我就不给了，大家都知道。
第二题：忙碌的售票员
题目描述：
小蓝是一家旅行社的售票员，他每天都很忙碌。
为什么呢？原因是这样的，当地文旅局与旅行社合作，所以旅行社能够以更低廉的价格拿到票，然后旅行社再将这些票配套导游服务一起卖给顾客。虽然看起来十分划算，但是这可苦了我们的售票员小蓝。因为即使能够得到更低价的票，但是票仍然需要从机器中打印出，文旅局的机器十分老旧，但是旅行社的订单又十分的多，这就导致了小蓝需要耗费大量的时间来打印票据。
文旅局共有3台打票机，每台机器每次只能打印1张票，打印一张票的时间是x分钟（即需要操作机器x分钟），但是机器每打印完一张票后，都需要停机y分钟，不然的话，机器会过热宕机，俗称“冷却”。
小蓝共有a张票需要打，同一时刻只能操作一台机器。他想知道，他最少需要多长时间才能打完所有的票。
输入格式：
第一行输入一个整数T(1 <= T <= 10^4)，代表测试数据组数。
接下来T行，每行3个整数x,y,a(1 <= x,y,a <= 10^7)，代表打票时间x，冷却时间y，共有a张票需要打。
输出格式：
输出T行，每行一个整数，代表最少需要多长时间可以打印完所有的票，单位为分钟。
参考答案：
t = int(input())
def sol():
for i in range(t):
x, y, a = map(int, input().split())
ans = 0
if 2 * x > y:
ans = x * a
else:
sv = (a - 1) // 3
rv = a - sv * 3
ans = rv * x + sv * (x + y)
print(ans)
sol()运行结果：
写一个解析：
这个代码主要是要想清楚这3台机器是怎么运行的。如果单次打印票据的时间为x，一开始，我们使用第一台机器进行打印，然后它休息需要y分钟，接着我们用第二台，使用完第二台后，机器一共运行了2x分钟，此时就要用第三台了，我们来考虑第一台，如果在这段时间内，两台机器运行的时间大于它休息的时间，那就可以继续无缝衔接地继续使用第一台，所以此时的条件是2x < y，那么这种情况下，打印全部票的最短时间就是x * a。然后我们当然是考虑2x > y的情况了，此时前两台机器都已经用过了，但是第一台机器还不能使用，所以只能把整个过程看作一个循环，3台机器运行完为一个循环，所以特殊情况特殊对待，我们可以将打印票据的过程分为两个部分计算，一个部分是打印剩余票据所需要的时间，记为rv * x，另一个部分是机器冷却所需要的时间，记为sv * (x + y)，其中rv表示剩余的未打印的票据数，sv表示需要进行冷却的次数。
基于每打印3张票就需要冷却一次的原则，具体来说，如果需要打印的票数是3的倍数，那么每打印三张就需要进行一次冷却，因此需要进行冷却的次数就是a // 3，如果需要打印的票数不是3的倍数，那么最后剩下的票数就不足3张，这些票就可以在最后一次冷却之前连续打印完，因此需要进行冷却的次数 就是(a - 1) // 3。ok，难理解的就是这几个点，剩下的我就不解释了。
第三题：兽之泪Ⅱ
题目描述：
在蓝桥王国，流传着一个古老的传说：在怪兽谷，由一笔由神圣骑士留下的宝藏。
小蓝是一位年轻而勇敢的冒险家，他决定去寻找宝藏，根据远古卷轴的提示，如果要找到宝藏，那么需要集齐n滴兽之泪，同时卷轴中也记载了，每击败一次怪兽，就能够收集一滴兽之泪。
小蓝知道，这些怪物并非泛泛之辈，每一只都拥有强大的力量和狡猾的技巧，每一只怪兽都要独特的弱点和对策，小蓝必须谨慎选择战斗的策略和使用的能量。
在怪兽谷中，有k只怪兽，对于第i只怪兽，第一次击败它需要xi点能量，再一次击败它需要yi点能量。在挑战过程中，前k - 1只怪兽可以随意挑战，但是第k只怪兽是怪兽之王，如果要挑战第k只怪兽，那么对于前k - 1只怪兽至少都要击败一次。
小蓝想知道，如果要集齐n滴兽之泪，那么至少需要多少能量。
输入格式：
第一行包含一个整数T（T <= 10^5），代表测试组数。
每组数据包含如下部分：
第一行包含两个整数k和n，表示怪物的数量和需要收集的兽之泪的数量。2 <= k <= 10^5,1 <= n <= 2 * 10^5。
接下来k行，每行包含两个整数xi和yi，表示第i只怪物第一次和后续击败所需要的能力(1 <= xi,yi <= 10^9)。
输出格式：
对于每组数据，输出一个整数，表示小蓝至少需要多少点能量才能收集完成。
参考答案：
import os
import sys
import heapq
from math import inf
import bisect
# 读取输入
t = int(input())
for _ in range(t):
k, n = list(map(int, input().split()))
q = []
res1 = 0 # 打兽之王
res2_2 = inf # 不打兽之王
number1 = []
number2 = []
for i in range(k):
x, y = list(map(int, input().split()))
res1 += x
number2.append(y)
if i == k - 1:
continue
heapq.heappush(q, (x, 1, i))
number1.append(x)
# 统计不打兽之王的结果
# 排序
new_number1 = sorted([[v, i] for i, v in enumerate(number1)])
# 前缀和
prefixsum = [0]
s = 0
for x, index in new_number1:
s += x
prefixsum.append(s)
# 枚举 y + 二分
for y, i in sorted([[y, i] for i, y in enumerate(number2[:-1])]):
index = bisect.bisect_left(new_number1, [y, -1])
# index 表示 y 前面的 x 的个数
if index >= n: # 说明，只选 x 就能把泪填满了
res2_2 = min(res2_2, prefixsum[n])
else:
if y < number1[i]: # 没有选到 y 的第一次
res2_2 = min(res2_2, prefixsum[index] + number1[i] + y * (n - 1 - index))
else:
res2_2 = min(res2_2, prefixsum[index] + y * (n - index))
if n < k: # 一定是不打兽之王
print(res2_2)
else:
print(min(res2_2, res1 + (n - k) * min(number2)))
运行结果：
这个题我灵感不错，但我没想到我的代码那么长，我来记录一下我的解题过程。
我用手写版本的。
好了，这篇就写到这里，算法双周赛的题太多了，我就先写这些，下一篇继续
