河南省第十届acm省赛-最小秘钥——个人c++解

怼烎@ 2022-06-15 05:17 126阅读 0赞

## 题目描述 ##

在中国近代史上，暂编\*\*\*军绝对是一支能打硬仗，大名鼎鼎的行动部队。“一二八”上海抗战，暂编\*\*\*军就曾打得小日本四易主帅。

\*月\*\*号，暂编\*\*\*军计划组成一个行动大队，派出N名队员潜伏在\*\*\*地，发动一次大规模的巷战行动。每名队员有自己的代号Ai，为了更好的配合作战，他们需要获得一个密钥Key,  然后各自迅速移动到Ai  MOD  Key位置，\*\*时刻一起开战。

作战方案已经定好，你能帮\*\*\*行动大队快速找个满足条件的最小密钥Key吗？

MOD表示取模运算，要求不能有多名队员待在同一个位置。

## 输入 ##

第一行： T        表示以下有T组测试数据             （ 1≤T ≤5 ）

对每组数据，

第一行：N     表示行动人员数  (1<=N<=3000)

接下来一行有N个整数，分别表示每个队员的代号Ai       (1<=Ai<=20000)

## 输出 ##

对每组测试数据，输出占一行，一个整数 Key.

## 样例输入 ##

1 2 3

4 6 9 10 13

## 样例输出 ##

#include<bits/stdc++.h>
    using namespace std;
    int b[20000];
    int mmm(int k)
    {
        int c;
        b[k]=b[k]+1;
        c=b[k];
        return c;
    }
    int main()
    {
        int a[3001];
        int t,n,i,j,k,c;
        scanf("%d",&t);
        while(t--)
        {
            memset(b,0,sizeof(b));
            scanf("%d",&n);
            for(i=0;i<n;i++)
            {
                scanf("%d",&a[i]);
            }
            for(j=2;;j++)//密钥从2开始寻找
            {
                for(i=0;i<n;i++)
                {
                    k=a[i]%j;//取余，此题相当于取模
                    c=mmm(k);//保存位置k出现的次数
                    if(c>1)break;//如果次数打于一，就打破循环
                }
                if(c<=1)break;//如果是正常退出就打破循环，找到最小密钥
                memset(b,0,sizeof(b));//非正常推出就将数组归零，重新寻找
            }
            printf("%d\n",j);
        }
    }