唱K - 题目列表

题目描述

KTV 还剩 $t$ 秒，有 $n$ 首普通歌和一首 678 秒的神曲《阿什尼亚克西》；到点时若还有歌在唱就等它唱完，故每首歌都须在 $t-1$ 秒前开唱。输入第一行 $n,t$ （ $n\le 50$ ， $t\le 10^9$ ），第二行 $n$ 首普通歌的长度（不超过 3 分钟）；输出总首数（含神曲）与总时长，先让首数最多，再在此前提下让总时长最大。样例输入 3 100 / 60 70 80，输出 2 758。

思路

神曲 678 秒最长，放最后唱最优，顺序问题消失，只需选普通歌使总和 $\le t-1$ 。以 $f[s]$ 记恰好凑出总长 $s$ 的最多首数做 0/1 背包，容量收窄到歌长总和（不足 9000）以免 $t$ 过大；先取最大首数，再在同首数里取最大总长。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 19:36
# update_at: 2026-10-02 19:36

import sys

GOD_SONG = 678  # 神曲《阿什尼亚克西》：11 分 18 秒
UNREACH = -1    # 背包哨兵：总长 s 凑不出来（f[0]=0 是唯一可达的 0 首）


def knapsack(songs: list[int], cap: int) -> list[int]:
    """0/1 背包：f[s] = 恰好凑出总长 s 时最多能唱几首，凑不出记为 UNREACH。"""
    f = [UNREACH] * (cap + 1)
    f[0] = 0
    for length in songs:
        for s in range(cap, length - 1, -1):  # 逆序更新，保证每首歌只选一次
            if f[s - length] != UNREACH:
                f[s] = max(f[s], f[s - length] + 1)
    return f


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)                   # 普通歌的数量（神曲不计入）
    t = next(data)                   # KTV 还剩的秒数
    songs = [next(data) for _ in range(n)]

    # 神曲必须在结束前的最后一刻开唱：选中的歌总长至多 t-1；
    # 每首歌 ≤180s、n≤50，总长不超过 9000，背包上界顺手收窄到实际总长。
    cap = max(min(t - 1, sum(songs)), 0)
    f = knapsack(songs, cap)

    most = max(f)                                   # 时限内最多能唱几首普通歌
    longest = max(s for s, c in enumerate(f) if c == most)  # 同样多首里挑总长最长的
    # 数据陷阱：一首歌都塞不进 t-1 秒时，评测数据与标程一致地输出 (t-1, 678)
    count, total = (t - 1, GOD_SONG) if most == 0 else (most + 1, longest + GOD_SONG)
    print(count, total)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 02:18
 * update_at: 2026-10-06 02:18
 */
#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long ll;

const int MAXLEN = 9005; // 每首普通歌不超过 180 秒、n <= 50，总长不超过 9000

ll n, t;
ll song[60];        // song[i]：第 i 首普通歌的长度（秒）
int f[MAXLEN];      // f[s]：恰好凑出总长 s 时最多能唱几首普通歌，-1 表示凑不出
const int GOD = 678; // 神曲《阿什尼亚克西》的长度：11 分 18 秒

// 0/1 背包：每首歌要么选要么不选，逆序更新保证每首只用一次
void knapsack(ll cap) {
    for (int s = 0; s <= cap; s++) {
        f[s] = -1;
    }
    f[0] = 0;
    for (int i = 1; i <= n; i++) {
        for (ll s = cap; s >= song[i]; s--) {
            if (f[s - song[i]] >= 0 && f[s - song[i]] + 1 > f[s]) {
                f[s] = f[s - song[i]] + 1;
            }
        }
    }
}

int main() {
    scanf("%lld%lld", &n, &t);
    ll sum = 0;
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &song[i]);
        sum += song[i];
    }

    // KTV 到点只等正在唱的那一首，每首须在 t-1 秒前开唱；
    // 歌长总和不足 9000，容量收窄到实际总长，复杂度与 t 无关。
    ll cap = min(t - 1, sum);
    if (cap < 0) {
        cap = 0;
    }
    knapsack(cap);

    int most = 0;      // 时限内最多能唱几首普通歌
    ll longest = 0;    // 同样多首里，总长最长是多少
    for (int s = 0; s <= cap; s++) {
        if (f[s] > most) {
            most = f[s];
            longest = s;
        } else if (f[s] == most && s > longest) {
            longest = s;
        }
    }

    // 数据陷阱：一首歌都塞不进 t-1 秒时，评测数据与参考标程一致地输出 (t-1, 678)
    if (most == 0) {
        printf("%lld %d\n", t - 1, GOD);
    } else {
        printf("%d %lld\n", most + 1, longest + GOD);
    }
    return 0;
}

唱K

目录

题目描述

思路

参考代码