题解 | #小美的外卖订单编号#

题目链接

小美的外卖订单编号

题目描述

美团商家的订单编号初始值为 $1$ 。每当发起一笔新订单时，编号自动加 $1$ 。为了防止编号无限增大，商家设置了一个编号上限 $m$ ：一旦当前订单编号加 $1$ 后大于 $m$ ，下一个订单的编号将重新从 $1$ 开始。

给定 $T$ 次询问，第 $i$ 次询问给出一对整数 $m$ 和 $x$ ，请你计算在编号上限为 $m$ 的情况下，第 $x$ 个订单的编号是多少。

解题思路

这是一个基础的周期性问题，可以通过模运算（取余）来解决。

分析编号规律

订单编号从 $1$ 开始，依次递增至 $m$ ，然后回到 $1$ ，形成一个周期。序列如下：

$1, 2, 3, \dots, m, 1, 2, 3, \dots, m, \dots$

这个序列的周期长度为 $m$ 。
建立数学模型

我们要求的是这个序列中的第 $x$ 个数。
- 标准的模运算是基于 $0$ 开始的序列（例如： $0, 1, \dots, m-1$ ）。
- 而本题的序列是基于 $1$ 开始的。
为了使用模运算，我们可以进行一个简单的转换：
- 将第 $x$ 个订单转换为从 $0$ 开始的索引，即 $x-1$ 。
- 然后对周期长度 $m$ 取模，得到 $(x-1) \pmod m$ 。这个结果的范围是 $[0, m-1]$ 。
- 最后，将结果转换回从 $1$ 开始的编号，即在取模结果上加 $1$ 。
因此，最终的计算公式为 $(x - 1) \pmod m + 1$ 。
处理多组查询

题目要求处理 $T$ 组独立的查询。我们只需编写一个循环，在循环内读取每组的 $m$ 和 $x$ ，然后套用上述公式计算并输出结果即可。

代码

c++
java
python

#include <iostream>

using namespace std;

int main() {
    int T;
    // 读取询问次数
    cin >> T;
    while (T--) {
        long long m, x;
        // 读取编号上限和订单序号
        cin >> m >> x;
        // 使用公式 (x - 1) % m + 1 计算并输出结果
        cout << (x - 1) % m + 1 << endl;
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 读取询问次数
        int T = sc.nextInt();
        for (int i = 0; i < T; i++) {
            // 读取编号上限和订单序号
            long m = sc.nextLong();
            long x = sc.nextLong();
            // 使用公式 (x - 1) % m + 1 计算并输出结果
            long ans = (x - 1) % m + 1;
            System.out.println(ans);
        }
    }
}

# 读取询问次数
T = int(input())
for _ in range(T):
    # 读取编号上限和订单序号
    m, x = map(int, input().split())
    # 使用公式 (x - 1) % m + 1 计算并输出结果
    print((x - 1) % m + 1)

算法及复杂度

算法：数学、模运算
时间复杂度：对于每次询问，计算都是常数时间的操作。总共有 $T$ 次询问，所以总时间复杂度为 $\mathcal{O}(T)$ 。
空间复杂度：算法只需要几个变量来存储输入和中间结果，因此空间复杂度为 $\mathcal{O}(1)$ 。