题目描述

题目：给定整数 1 到 n 的范围，要求从中选择 k 个数，计算能够获得的最大积分。计分规则如下：初始积分为 0，每当选取的整数 i 满足 i+1 未被选取时，积分增加 1。
- 输入描述：第一行输入一个整数 T（ $1 \leq T \leq 10^5$ ），表示测试数据的组数。接下来的 T 行中，每行包含两个整数 n 和 k（ $1 \leq k \leq n \leq 10^{12}$ ），分别表示整数的范围和需要选取的个数。
- 输出描述：对于每组测试数据，输出一个整数，表示该组测试数据下所能获得的最大积分。
输入输出示例
- 输入
  1
  2
  3
  2
  1 1
  4 2
- 输出
  1
  2
  1
  2

解题思想

问题分析
- 核心规则：为了获得最大积分，最优的策略是尽量让所选的数字相互隔开。
- 案例分析-1
  - 当 n = 4 且 k <= 2，我们可以按照 [√, ×, √, ×] 或 [×, √, ×, √] 的方式选取，这两种方式都能获得最大积分，即 k。
  - 当 n = 5 且 k <= 3，我们可以按照 [√, ×, √, ×, √] 的方式选取，获得最大积分为 k。
  - 推广可得，如果 $k \le \lceil n/2 \rceil$ ，可以保证每个选择的数字隔相互开，此时最大积分等于 k。
- 案例分析-2
  - 当 n = 4 且 k > 2，我们可以 ① 先按照 [√, ×, √, ×] 的方式选取 2 个数字；② 再从后向前选择剩下的 k - 2 个数字。在 ① 时，我们获取积分为 2；在 ② 时，选中第一个未被选中的数字时积分不变，从第二个开始，每选中一个数字，积分在当前积分的基础上减 1。
  - 当 n = 5 且 k > 3 时，我们可以 ① 先按照 [√, ×, √, ×, √] 的方式选取 3 个数字；② 再从后向前选择剩下的 k - 3 个数字。在 ① 时，我们获取积分为 3；在 ② 时，每选中一个数字，积分在当前积分的基础上减 1。
  - 推广可得，如果 $k \ge \lceil n/2 \rceil$ ，当 n 是偶数时，最大积分等于 $2 \lceil n/2 \rceil - k + 1$ ，当 n 是奇数时，最大积分等于 $2 \lceil n/2 \rceil - k$ 。
积分计算公式

$maxScore = \begin{cases} k & k\le k_{max}\\ 2k_{max}-k+1 & k>k_{max}\text{ and }k\text{ 是偶数}\\ 2k_{max}-k & k>k_{max}\text{ and }k\text{ 是奇数 } \end{cases}$

其中， $k_{max} = \lceil n/2 \rceil$ 表示在最优选取方式下，最多可以选取 $k_{max}$ 个数字以获得满分。也就是说，当 $k \in [1, n]$ 且取值为 $k_{max}$ 时，可以达到最大的积分。
时间复杂度：对每组测试数据 $(n,k)$ ，时间复杂度为 $O(1)$ 。

代码实现

export default function maxScore(n, k) {
  const kMax = Math.ceil(n / 2);

  if (k <= kMax) return k;
  else if (n % 2 === 0) return 2 * kMax - k + 1;
  else return 2 * kMax - k;
}

单元测试

import { describe, test } from "node:test";
import { strict as assert } from "node:assert";
import maxScore from "./选数I.mjs";

describe("选数I", () => {
  test("基础用例", () => {
    assert.equal(maxScore(1, 1), 1);
    assert.equal(maxScore(2, 1), 1);
    assert.equal(maxScore(3, 2), 2);
    assert.equal(maxScore(4, 2), 2);
    assert.equal(maxScore(4, 3), 2);
    assert.equal(maxScore(5, 3), 3);
  });
  test("边界用例", () => {
    assert.equal(maxScore(10, 5), 5);
    assert.equal(maxScore(10, 6), 5);
    assert.equal(maxScore(10, 10), 1);
  });
  test("较大输入", () => {
    assert.equal(maxScore(1000000000000, 500000000000), 500000000000);
    assert.equal(maxScore(1000000000000, 600000000000), 400000000001);
  });
});