[语言月赛 202411] K/D/A 的题解

记住只在没有思路时使用题解，不要从它复制粘贴代码。请尊重题目和题解的作者。
在解题之前提交题解的代码会导致封禁。

作者： admin

概述

本题要求根据每名战士的三个参数 $K, D, A$ ~K, D, A~，按题面给定的三档规则算出各自的实力，并输出实力最高者的编号（保证最高者唯一）。核心解法是按 $K-D$ ~K-D~ 与 $K$ ~K~、 $D$ ~D~ 的大小关系套用对应档位的公式逐名算分，再用打擂台的方式在线维护最大值及其下标。

分析

核心观察

每名战士的实力只由他自己的 $K, D, A$ ~K, D, A~ 决定，与其他人无关，因此可以边读入边算出实力，只需要记住“目前的最大值”和“取到它的编号”。三档公式的判定有先后顺序：先看 $K-D$ ~K-D~ 是否达到 $10$ ~10~，不满足时才去看 $K$ ~K~ 是否不小于 $D$ ~D~。

思路

设第 $i$ ~i~ 名战士的参数为 $K_i, D_i, A_i$ ~K_i, D_i, A_i~，题面给出的实力计算规则是一个分段函数：

$\displaystyle f(K,D,A)=\begin{cases} K\times(K-D)+A, & K-D\ge 10,\\ (K-D+1)\times 3+A, & K-D<10 \text{ 且 } K\ge D,\\ A\times 2, & K<D. \end{cases}$

三段按顺序判定。第二段是“否则，若 $K\ge D$ ~K\ge D~”，它的完整前提是 $K-D<10$ ~K-D<10~ 且 $K\ge D$ ~K\ge D~；当 $K<D$ ~K<D~ 时必然有 $K-D<0<10$ ~K-D<0<10~，所以剩下的情况就是 $K<D$ ~K<D~，对应第三段。判定顺序不可交换：若先判 $K\ge D$ ~K\ge D~，那么 $K-D=10$ ~K-D=10~ 这类应当走第一档的数据会被错误地送进第二档。

三段的取值都不小于 $0$ ~0~：第一段中 $K-D\ge 10$ ~K-D\ge 10~ 且 $K\ge 0$ ~K\ge 0~，乘积与加数均非负；第二段中 $K\ge D$ ~K\ge D~ 保证 $K-D+1\ge 1$ ~K-D+1\ge 1~，乘 $3$ ~3~ 后也非负；第三段是 $A\times 2\ge 0$ ~A\times 2\ge 0~。由数据范围 $0\le K_i,D_i,A_i\le 10000$ ~0\le K_i,D_i,A_i\le 10000~ 可得实力的最大值出现在 $K=10000, D=0$ ~K=10000, D=0~ 处，为

$\displaystyle 10000\times(10000-0)+10000=100010000$

实力最高的战士唯一，所以逐个比较时用严格大于即可，不必处理并列。

由于只需要最强者的编号，不必保存全部实力：读入一名战士就算出他的实力 $v$ ~v~，与当前最大值比较，只在 $v$ ~v~ 严格更大时把它记为新的最大值并更新答案下标。朴素做法是先把 $n$ ~n~ 名战士的信息全部存下来，再扫一遍求最大值及其下标，时间同为 $O(n)$ ~O(n)~，但空间需要 $O(n)$ ~O(n)~；边读边算把空间降到了 $O(1)$ ~O(1)~。

具体示例

以样例 $1$ ~1~ 为例。第 $1$ ~1~ 名战士 $K=5, D=3, A=8$ ~K=5, D=3, A=8~，此时 $K-D=2<10$ ~K-D=2<10~ 但 $K\ge D$ ~K\ge D~，走第二档，实力为

$\displaystyle (5-3+1)\times 3+8=17$

第 $2$ ~2~ 名战士 $K=3, D=4, A=7$ ~K=3, D=4, A=7~，此时 $K<D$ ~K<D~，走第三档，实力为 $7\times 2=14$ ~7\times 2=14~。第 $3$ ~3~ 名战士 $K=3, D=3, A=13$ ~K=3, D=3, A=13~，此时 $K-D=0<10$ ~K-D=0<10~ 且 $K\ge D$ ~K\ge D~，走第二档，实力为 $(3-3+1)\times 3+13=16$ ~(3-3+1)\times 3+13=16~。三者中 $17$ ~17~ 最大，对应第 $1$ ~1~ 名战士，故输出 $1$ ~1~。

样例 $2$ ~2~ 的两名战士恰好落在 $K-D$ ~K-D~ 的分界线两侧： $K=10, D=1, A=9$ ~K=10, D=1, A=9~ 的 $K-D=9$ ~K-D=9~，不满足 $K-D\ge 10$ ~K-D\ge 10~，走第二档得 $(10-1+1)\times 3+9=39$ ~(10-1+1)\times 3+9=39~； $K=10, D=0, A=1$ ~K=10, D=0, A=1~ 的 $K-D=10$ ~K-D=10~，满足第一档得 $10\times 10+1=101$ ~10\times 10+1=101~。第一档的 $101$ ~101~ 更大，故输出 $2$ ~2~。两人的 $K-D$ ~K-D~ 只差 $1$ ~1~，却分属两个档位。若把判据误写成 $K-D>10$ ~K-D>10~，第 $2$ ~2~ 名战士就会被判入第二档，实力只有 $(10-0+1)\times 3+1=34$ ~(10-0+1)\times 3+1=34~，反而小于第 $1$ ~1~ 名的 $39$ ~39~，答案会错成 $1$ ~1~。可见分界处的等号必须取对。

样例 $3$ ~3~ 中两名战士的 $K-D$ ~K-D~ 都等于 $3$ ~3~，第二档的 $(K-D+1)\times 3$ ~(K-D+1)\times 3~ 都是 $12$ ~12~，实力分别为 $12+3=15$ ~12+3=15~ 与 $12+2=14$ ~12+2=14~，胜负完全由 $A$ ~A~ 决定： $A$ ~A~ 在第二档里是加项而不是乘数。

算法步骤

读入战士人数 n。
令当前最大值 best 为 $-1$ ~-1~，答案下标 ans 为 $1$ ~1~。
对 i 从 $1$ ~1~ 到 n：读入第 i 名战士的 k、d、a，按先后次序判断分档并算出实力 v —— 若 $k-d\ge 10$ ~k-d\ge 10~ 则 v 为 $k\times(k-d)+a$ ~k\times(k-d)+a~；否则若 $k\ge d$ ~k\ge d~ 则 v 为 $(k-d+1)\times 3+a$ ~(k-d+1)\times 3+a~；否则 v 为 $a\times 2$ ~a\times 2~。
若 v 严格大于 best，则把 best 更新为 v，把 ans 更新为 i。
输出 ans。

复杂度分析

时间： $O(n)$ ~O(n)~，每名战士只做常数次比较与算术运算。
空间： $O(1)$ ~O(1)~，只用到人数、当前最大值、答案下标以及当前战士的参数等常数个变量。

实现注意事项

每行形如 $K/D/A$ ~K/D/A~，把分隔符 $/$ ~/~ 直接写进格式串即可一次读入三个整数，例如 $\%d/\%d/\%d$ ~\%d/\%d/\%d~，不必先把整行读成字符串再手工切分。
三个分支的顺序不能颠倒：必须先判 $K-D\ge 10$ ~K-D\ge 10~，再判 $K\ge D$ ~K\ge D~，剩下的才是 $K<D$ ~K<D~。先判 $K\ge D$ ~K\ge D~ 会让 $K-D\ge 10$ ~K-D\ge 10~ 的数据走错档位。
分界处要取等号： $K-D=10$ ~K-D=10~ 属于第一档， $K-D=9$ ~K-D=9~ 属于第二档； $K=D$ ~K=D~ 时 $K-D+1=1$ ~K-D+1=1~，属于第二档。
实力最小为 $0$ ~0~（如 $K=0, D=1, A=0$ ~K=0, D=1, A=0~ 时 $0\times 2=0$ ~0\times 2=0~），把当前最大值初始化为 $-1$ ~-1~ 可以保证第一个战士一定会触发更新。
比较必须用严格大于。虽然题目保证实力最高者唯一，但只要写法上不取等号，即使出现并列也会稳定地保留较小编号。
实力上界为 $100010000$ ~100010000~，未超出 $32$ ~32~ 位有符号整数的范围，标程仍统一用 long long 存放实力并在乘法处做类型提升，留出余量。
输出只有一个整数，注意行末换行。
$n$ ~n~ 最大为 $100000$ ~100000~，使用 scanf 与 printf 的读入写出方式足以应对，不需要额外的读入优化。

源代码

#include <cstdio>

int main() {
    int n;
    if (scanf("%d", &n) != 1) return 0;

    long long best = -1;
    int ans = 1;
    for (int i = 1; i <= n; ++i) {
        int k = 0, d = 0, a = 0;
        if (scanf("%d/%d/%d", &k, &d, &a) != 3) return 0;

        long long v;
        if (k - d >= 10)
            v = 1LL * k * (k - d) + a;
        else if (k >= d)
            v = 1LL * (k - d + 1) * 3 + a;
        else
            v = 1LL * a * 2;

        if (v > best) {
            best = v;
            ans = i;
        }
    }
    printf("%d\n", ans);
    return 0;
}

import sys


def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    best = -1
    ans = 1
    for i in range(1, n + 1):
        k, d, a = map(int, data[i].split('/'))
        if k - d >= 10:
            v = k * (k - d) + a
        elif k >= d:
            v = (k - d + 1) * 3 + a
        else:
            v = a * 2
        if v > best:
            best = v
            ans = i
    print(ans)


main()

目前没有评论。