滴滴编程题¶

第一题：紧急降温¶

时间限制： C/C++ 语言 1000MS；其他语言 3000MS
内存限制： C/C++ 语言 65536KB；其他语言 589824KB

题目描述¶

某大型数据中心的机房内共有 N 台服务器正在运行，由于负载过高，它们都出现了过热现象。第 i 台服务器目前的过热指数为 hᵢ。为了保证设备安全，必须将所有服务器的过热指数降低到 0 或以下。

作为机房管理员，你拥有一套强力的应急制冷系统。每次启动该系统，你需要指定一台服务器作为制冷中心，系统会产生如下效果：

被选为制冷中心的服务器，其过热指数减少 A。
机房内的其他所有服务器（除中心外的），其过热指数减少 B。（满足 A > B）

为了使所有服务器的过热指数都降至 0 或更低，请计算最少需要启动多少次制冷系统。

输入描述¶

输入包含 N+1 行。

第一行包含三个整数 N、A、B，分别表示服务器的数量、中心制冷量和环境制冷量。

接下来的 N 行，每行包含一个整数 hᵢ，表示第 i 台服务器初始的过热指数。

1 ≤ N ≤ 10⁵，1 ≤ B < A ≤ 10⁹，1 ≤ hᵢ ≤ 10⁹。

输出描述¶

输出一行一个整数，表示最少需要的操作次数。

样例输入¶

样例输出¶

提示¶

可以进行如下两次操作将所有服务器降温：

选择过热指数为 8 的服务器作为中心。各服务器过热指数变为：8−5=3，7−3=4，4−3=1，2−3=−1。此时只有第 4 台服务器恢复正常。
选择剩余过热指数为 4 的服务器作为中心。各服务器过热指数变为：3−3=0，4−5=−1，1−3=−2，−1−3=−4。此时所有服务器均已恢复正常。

解法思路¶

使用二分答案。

假设执行 k 次操作，相当于：

所有服务器都降低 k × B；
每次选为中心的服务器，额外降低 A - B。

对于服务器 h，如果 h > k × B，至少需要被选为中心 \(\lceil \frac{h-kB}{A-B} \rceil\) 次。将所有服务器需要的次数相加：

总次数 ≤ k：可以在 k 次操作内完成，剩余次数任意分配即可。
总次数 > k：无法完成。

操作次数越多，越容易满足条件，因此可以二分查找最小可行值。
二分上界取 ⌈max(h) / B⌉，因为此时仅靠所有服务器每次至少降低 B 就足够。
设 \(H=\max(h_i)\)，\(U=\lceil H/B\rceil\)：

时间复杂度： \(O(N\log(U+1))\)。
空间复杂度： \(O(N)\)，用于存储输入；二分过程额外空间为 \(O(1)\)。

第二题：花束设计¶

时间限制： C/C++ 语言 1000MS；其他语言 3000MS
内存限制： C/C++ 语言 65536KB；其他语言 589824KB

题目描述¶

花店里有 N 朵鲜花，每朵花都有两个属性：品种 tᵢ 和美丽度 dᵢ。你需要从中恰好挑选 K 朵花来制作一束花束。

为了评价这束花的整体品质，我们定义“总评分”为以下两部分的和：

基础美丽值： 所选 K 朵花的美丽度之和。
多样性奖励： 如果你选出的花中包含了 x 种不同的品种，那么奖励分数为 x*x。

请你计算一下，如何挑选花朵，才能使得花束的总评分最大？

输入描述¶

输入包含 N+1 行。

第一行包含两个整数 N 和 K，分别表示鲜花的总数量和需要挑选的数量。

接下来的 N 行，每行包含两个整数 tᵢ 和 dᵢ，分别表示第 i 朵花的品种编号和美丽度。

1 ≤ K ≤ N ≤ 10⁵，1 ≤ tᵢ ≤ N，1 ≤ dᵢ ≤ 10⁹。

输出描述¶

输出一行一个整数，表示能够获得的最大总评分。

样例输入¶

样例输出¶

提示¶

如果你选择第 1、第 2 和第 3 朵花：

基础美丽值之和为 9+7+6=22。
包含的品种为 1 和 2，共 2 种不同品种，因此多样性奖励为 2*2=4。
总评分为 22+4=26。

这是能够达到的最大值。

解法思路¶

使用排序 + 贪心替换。

将所有花按美丽度从大到小排序，先选前 K 朵，使美丽度总和最大。
记录已选品种。对于同品种中多余的花，将美丽度存入栈。由于按降序遍历，栈顶就是可以替换的最小美丽度。
继续遍历剩余的花：
- 如果品种已经选过，跳过。
- 如果是新品种，就用它替换栈顶的重复花，使品种数量增加 1。
- 每次替换后计算美丽度总和 + 品种数²，更新答案。

每次引入新品种，都选择剩余花中美丽度最大的，并移除可替换花中美丽度最小的，因此能得到各个可行品种数量下的最大美丽度总和。

注意：即使某次替换后评分下降，也要继续尝试，后续增加品种仍可能得到更高评分。

时间复杂度： \(O(N\log N)\)，主要来自排序。
空间复杂度： \(O(N)\)，用于存储鲜花、品种集合及重复花栈。

import sys

def solve():
    input = sys.stdin.readline
    n, k = map(int, input().split())
    flowers = [tuple(map(int, input().split())) for _ in range(n)]
    flowers.sort(key=lambda flower: flower[1], reverse=True)

    seen = set()
    duplicates = []
    total = 0

    for i in range(k):
        t, d = flowers[i]
        total += d
        if t in seen:
            duplicates.append(d)
        else:
            seen.add(t)

    kinds = len(seen)
    answer = total + kinds * kinds

    for i in range(k, n):
        if not duplicates:
            break

        t, d = flowers[i]
        if t in seen:
            continue

        # 栈顶是已选重复花中美丽度最小的
        total += d - duplicates.pop()
        seen.add(t)
        kinds += 1
        answer = max(answer, total + kinds * kinds)

    print(answer)


if __name__ == "__main__":
    solve()