题解 P1154 【奶牛分厩】

· · 题解

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

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

来，理解一下题目。

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

这句话可以得出，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;
 }