奶牛分厩题解

题目描述

农夫约翰有 N(1≤N≤5000)头奶牛，每头奶牛都有一个唯一的不同于其它奶牛的编号 s[i]，所有的奶牛都睡在一个有 K 个厩的谷仓中，厩的编号为 00 到 K−1。每头奶牛都知道自己该睡在哪一个厩中，因为约翰教会了它们做除法，Si mod K的值就是第 i 头奶年所睡的厩的编号。

给出一组奶牛的编号，确定最小的 K 使得没有二头或二头以上的奶牛睡在同一厩中。

输入格式

第一行一个正整数 N，第 22 到 N+1行每行一个整数表示一头奶牛的编号。

输出格式

一个整数，表示要求的最小的 K，对所有的测试数据这样的 K是一定存在的。

输入输出样例

输入 #1

5 
4 
6 
9 
10 
13 

输出 #1

8

这道题目看起来很难的样子，但是只要你看懂了题目，想到了该用什么定理来实现，这就是一道水题。

无论什么数论题，只要你想到了相关的定理，在加以推导，得出在这道题目相对应的式子，你，就赢了！

来，理解一下题目。

“使得没有二头或二头以上的奶牛睡在同一厩中。”（题目原话）

这句话可以得出，ans>=n，没毛病吧，兄弟

“Si mod K的值就是第ii头奶年所睡的厩的编号。”

得出了这个

核心定理：c%b=(a%b+(c+a)%b)%b

就是说我们只要求出所有数的差

再从小到大搜索，只要有一个数不为任何两头牛的差，就可以输出答案了

#include<bits/stdc++.h>
using namespace std;
int a[1000010],b[1000010],n;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];//输入
    }
    for(int i=1;i<=n;i++)
    {
        for(int u=1;u<=n;u++)
        {
            b[abs(a[u]-a[i])]=1;//求出差值，并标记
        }
    }//为什么用abs而不用sort?就是因为sort太Tm慢了
    for(int i=n; ;i++)//从n开始搜索
    {
        if(b[i]==0)
        {
            cout<<i;//输出
            return 0;//break也可以，你开心就好
        }
    }
    return 0;
 }

在百忙之中写一篇题解也比较辛苦，别忘了点个赞！