码蹄集 - MT1274 · 买马

• • 买马
  • • 题目描述
    • 输入描述
    • 输出描述
    • 样例一
    • • 输入
      • 输出
• 题目分析
• AC代码

• 买马

时间限制：1000 ms
空间限制：65535 KB

在市场当中，每一个编号为i的马都住在相应编号为i的马厩中，现在小码哥想要在市场里购买一定数量的马匹，由于市场很大，小码哥可以买回编号非常大的马匹回来，但是小码哥的牧场并没有这么大，使得马匹住在相应编号的马厩中。但聪明的小码哥想到可以使用某种哈希映射来解决该问题。他想出的方法是对它们进行取模操作（即编号为si的马住在小码哥家编号为 si mod k的马厩里）。现在已经知道了买回来马匹的编号，你是否可以找到一个最小的k来完成此映射，使得每一匹马单独住在一个马厩中。(注意小码哥家有编号为0的马厩)

第一行一个整数n表示小码哥买回来马匹的总数。（马的数量不超过100）
接下来n行，每一行一个数字si表示第i匹马的编号。(马的编号为不超过1000的正整数)

一个整数，表示要求的最小的 K

3
1
2
6

3

这道题大概意思就是：

给你 n n n 个数，其中第 i i i个数是 n i n_i ni​。

让你找到一个最小的正整数 a n s ans ans，使得 n i % a n s n_i % ans ni​%ans 各不相同。

n n n的范围是 0 ∼ 100 0sim100 0∼100， n i n_i ni​的范围是 0 ∼ 1000 0sim1000 0∼1000，所以要找的 a n s ans ans一定 ≤ 1001 leq1001 ≤1001。

从 1 1 1开始暴力枚举 a n s ans ans即可，直到找到一个不冲突的 a n s ans ans就是答案。

#include 
using namespace std;
#define mem(a) memset(a, 0, sizeof(a))
#define dbg(x) cout << #x << " = " << x << endl
#define fi(i, l, r) for (int i = l; i < r; i++)
#define cd(a) scanf("%d", &a)
typedef long long ll;
int a[111];  // 用来记录n匹马的编号
int main() {
    int n;
    cin >> n;
    fi (i, 0, n)  // for (int i = 0; i < n; i++)
        cd(a[i]);  // scanf("%d", &a[i]);
    int ans = 1;  // 从1开始尝试
    while (true) {
        set appended;  // 已经出现过的
        for (int i = 0; i < n; i++) {
            if (appended.count(a[i] % ans)) {  // 如果已经出现过
                goto loop;
            }
            appended.insert(a[i] % ans);  // 没有跳到loop，就说明之前还没有没有出现过。现在，他出现过了，所以要添加到appended中
        }
        cout << ans << endl;  // n匹马全部遍历完了都没有冲突，ans就是答案
        break;
        loop:  // ans不可行的时候强制跳到这里
        ans++;
    }
    return 0;
}

每周提前更新菁英班周赛题解，点关注，不迷路

原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/124850224