题解 | #选数#_牛客博客

题目链接

选数

题目描述

给定两个整数 $n$ 和 $k$ 。我们需要从 $1$ 到 $n$ 的 $n$ 个整数中选择 $k$ 个数。计分规则如下：对于每一个被选中的数 $x$ ，如果 $x-1$ 没有被选中，那么积分就加一。我们的目标是求出可能得到的最大积分。

输入:

第一行一个整数 $T$ ，表示数据组数。
接下来 $T$ 行，每行两个整数 $n$ 和 $k$ 。

输出:

对每组数据输出一个整数，表示最大积分。

解题思路

这是一个贪心思想的题目。我们来分析一下计分规则：

每当选中一个数 $x$ ，而 $x-1$ 未被选中时，就得 1 分。
这其实等价于：我们选出的 $k$ 个数会形成若干个连续的数字段（例如，选择 {2, 3, 5, 6, 7}，会形成 {2, 3} 和 {5, 6, 7} 两个连续段）。
每个连续段的第一个数（最小值） $x$ 必然满足 " $x-1$ 未被选中"（除非 $x=1$ ），因此每个连续段都会贡献 1 分。
所以，总积分就等于我们构造出的连续段的个数。

我们的目标变成了：用 $k$ 个数，在 $1$ 到 $n$ 的范围内，构造出尽可能多的连续段。

一个显然的上限：我们总共只选了 $k$ 个数，所以最多也只能构造出 $k$ 个连续段（每个段只包含一个数）。因此，最大积分不可能超过 $k$ 。
另一个上限：我们如何分隔连续段？是用那些没有被选中的数。我们有 $n-k$ 个未选中的数。这 $n-k$ 个数最多能作为“隔板”，将选中的数分成 $n-k+1$ 个部分。因此，最大积分也不可能超过 $n-k+1$ 。

结合以上两个上限，我们可以得出结论，最大积分就是这两个值的较小者。

最终答案就是 $\min(k, n - k + 1)$ 。

代码

c++
java
python

#include <iostream>
#include <algorithm>

using namespace std;

void solve() {
    long long n, k;
    cin >> n >> k;
    cout << min(k, n - k + 1) << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

import java.util.Scanner;
import java.lang.Math;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            long n = sc.nextLong();
            long k = sc.nextLong();
            System.out.println(Math.min(k, n - k + 1));
        }
    }
}

t = int(input())
for _ in range(t):
    n, k = map(int, input().split())
    print(min(k, n - k + 1))

算法及复杂度

算法：数学 / 贪心
时间复杂度：对于每组测试数据，计算是 $\mathcal{O}(1)$ 的。总时间复杂度为 $\mathcal{O}(T)$ ，其中 $T$ 是数据组数。
空间复杂度： $\mathcal{O}(1)$