题解 P1154 【奶牛分厩】

Mars_Dingdang · 2020-08-06 12:06:12 · 题解

来考古啦~~~

话说为什么这一题的题解这么少？这一题就是取模的一个变型。

题目大意

有 N(1 \le N \le 5000) 头奶牛，每头奶牛都有一个唯一的不同于其它奶牛的编号 s_i，所有的奶牛都睡在一个有 K 个厩的谷仓中，厩的编号为 0 到 K-1。S_i \bmod K 的值就是第 i 头奶年所睡的厩的编号。

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

大体思路

倒推，若有两头牛在同一个厩里，设这两头牛的编号为 a,b，则 a≡b(\bmod \ k) =>a-b≡0(\bmod \ k)=>k|a-b。说明只要有两个数的差等于 k，就无法满足。因此本题的条件为：∨a,b∈S 存在 |a-b|≠k。因此可以记录所有 |a-b|的可能值，从而找到最小的 k。

同时，因为厩的数量显然比奶牛的数量多，因此还需满足 n\le k。

输入：

int n;
cin>>n;
for(int i=1;i<=n;i++) 
    cin>>a[i];//记录奶牛的编号

记录差值 注意差值是两个数的绝对值。绝对值函数为abs()，如果不想加绝对值则须用sort先进行排序。

for(int i=1;i<=n;i++){
    for(int j=i+1;j<=n;j++){//遍历所有奶牛
        int t=abs(a[i]-a[j]);
        //记录差值
        sub[t]=1;//将差值标记为1
        //说明k无法取到这个值。
    }
}

确定 k

    int k=n;
    //因为厩的数量显然比奶牛的数量多，  //所以从n开始找
    while(1){
        if(sub[k]==0){
        //若这个差值不存在
        //则表明满足条件
            cout<<k;
            return 0;//输出并结束
        }
        k++;//每次让k+1
    }

完整代码：

#include<bits/stdc++.h>//头文件
using namespace std;
int a[5005];//记录编号
bool sub[1000005];//记录差值是否存在
//因此用bool节省空间
//（用int也不会MLE）
int main(){
    int n;
    cin>>n;//输入
    for(int i=1;i<=n;i++) cin>>a[i];//输入编号
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){//遍历所有奶牛
            int t=abs(a[i]-a[j]);
            sub[t]=1;//记录差值
        }
    }
   int k=n;//从n开始找
    while(1){
        if(sub[k]==0){//k满足条件
            cout<<k;输出并结束程序
            return 0;
        }
        k++;
    }
    return 0;
}

由于题目保证对所有的测试数据这样的 K 是一定存在的，因此不用担心死循环。

看得这么认真，不点个赞再走嘛qaq