【P1373】奶牛的卧室

看山神的题解写出来的，sro_dydxh_orz

原题：奶牛们有一个习惯，那就是根据自己的编号选择床号。如果一头奶牛编号是a，并且有0..k-1一共k张床，那么她就会选择a mod k号床作为她睡觉的地点。显然，2头牛不能睡在一张床上。那么给出一些奶牛的编号，请你为她们准备一间卧室，使得里面的床的个数最少。

n(1<=n<=5000)，Si(1<=Si<=1000000)

题意就是对于任意一个num[i]<num[j]，求一个m，使得num[i]%m!=num[j]%m

然后就可以把上面内个式子变一下：(num[i]-num[j])%m!=0

也就是任意一对大于0的差%m!=0

所以先给num排个序，答案在[n,num[n]]内

枚举答案验证，如果满足上面的条件，就输出

然而会T

怎么优化呐

用一个类似于筛法的方法，用一个flag记录那些差没有出现，然后预处理所有的差（一点需要注意的地方，因为排好序了所以j要枚举到<i）

然后枚举[n,num[n]]，如果i没有出现，还不能直接说是答案，要枚举i的倍数，如果i的倍数出现过，依旧不能作为答案

为什么呐

设i的倍数是i*c且出现过，因为i*c出现过，所以可设i*c=num[p]-num[q]，则(num[p]-num[q])%i = i*c%i = c != 0，就不满足上面的条件

山神在一开始的时候把1-(n-1)标记为出现过了，我觉得没有必要吧，因为枚举答案是从n-num[n]枚举的

代码：

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 using namespace std;

 int read(){int z=,mark=;  char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')mark=-;  ch=getchar();}

     while(ch>=''&&ch<=''){z=(z<<)+(z<<)+ch-'';  ch=getchar();}

     return z*mark;

 }

 int n,a[];

 bool flag[];

 int main(){//freopen("ddd.in","r",stdin);

     memset(flag,,sizeof(flag));

     cin>>n;

     for(int i=;i<=n;i++){  a[i]=read();  flag[i]=true;}

     flag[n]=false;

     sort(a+,a+n+);

     for(int i=;i<=n;i++)

         for(int j=;j<i;j++)

             if(!flag[a[i]-a[j]])

                 flag[a[i]-a[j]]=true;

     for(int i=n;i<=a[n];i++){

         if(!flag[i])

             for(int k=i*;k<=a[n];k+=i)if(flag[k]){  flag[i]=true;  break;}

         if(!flag[i]){  cout<<i<<endl;  return ;}

     }

     cout<<a[n]<<endl;

     return ;

 }

巴特西

【P1373】奶牛的卧室

最新文章

热门文章