题目链接

小美的外卖订单编号

题目描述

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

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

解题思路

这是一个典型的周期性问题，可以通过取模运算高效解决。

  1. 识别周期：订单编号从 1 到 m 循环出现，形成了一个长度为 m 的固定周期。序列看起来像这样：1, 2, ..., m, 1, 2, ...。
  2. 定位问题：我们需要找到这个无限序列中第 x 个位置的数字是什么。
  3. 坐标转换：在数学中，取模运算 a % m 的结果通常在 [0, m-1] 区间内。而我们的编号序列是从 1 开始的（1-indexed）。为了使用取模运算，我们首先需要将第 x 个位置转换为从 0 开始的索引，即 x - 1。
  4. 执行取模：对转换后的索引进行取模运算 (x - 1) % m，得到的结果就在 0 到 m-1 之间。这个结果对应了周期内从0开始的位置。
  5. 映射回原序列：最后，将取模得到的结果加 1，即可映射回 1 到 m 的实际订单编号。
  6. 最终公式：综合起来，计算公式为 (x - 1) % m + 1。
  7. 数据类型：考虑到 x 的值可能很大，为防止整数溢出，应使用 long long (C++) 或 long (Java) 等64位整型来存储。

代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        LL m, x;
        cin >> m >> x;
        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();
        while (t-- > 0) {
            long m = sc.nextLong();
            long x = sc.nextLong();
            long result = (x - 1) % m + 1;
            System.out.println(result);
        }
    }
}

t = int(input())

for _ in range(t):
    m, x = map(int, input().split())
    result = (x - 1) % m + 1
    print(result)

算法及复杂度

  • 算法：数学、模运算
  • 时间复杂度：，其中 是询问的次数。对于每次询问，计算都是常数时间 。
  • 空间复杂度：，我们只需要常数级别的额外空间来存储变量。