codeforce303C-Minimum Modular-剪枝，暴力

Minimum Modular

题意：就是在一堆数字中，每一个数字对m取模不能等于这堆数字中的其他数字，同时给了K个机会可以删除一些数字。求最小的m；

思路：我一开始完全没思路，队长说的并查集什么的不会，于是就看了看别人的题解，看到可以用暴力剪枝的做法；

　　至于减枝的做法就是；

　　　　首先想到暴力，从小到大枚举m，然后判断n个数中对m取模同余个数有多少，如果超出k就枚举更大的m。然而这样的话，时间复杂度为O（n*1e6）。然后在网上找了博客看，但是有些地方当时自己感觉很不好理解的，这里做下自己的解释。1.首先这里用了一个剪枝，这个剪枝能节省大量时间。因为如果有k+1个数都是对m取模同余，那么只需删除k个数，就可以让剩下的数（只剩下一个数）不同余，那么从k+1个同余的数中取出2个数组成同余对的组合数就有C（2，k+1）种，即k*k+1/2种，那么如果对m取模同余的同余对的组合数大于k*k+1/2种，说明无法删除k个数使得剩下的数不同余。2.然后暴力判断此时满足1步骤的m作为模是否能满足同余的数小于k个。

　　

#include <cstdio>

#include <iostream>

#include <cstring>

#include <string>

#include <algorithm>

using namespace std;

const int maxn = +;

int a[maxn],n,k,re[maxn],h[maxn];

int main(){

    scanf("%d%d",&n,&k);

    int max = -;

    memset(re,,sizeof(re));

    memset(h,,sizeof(h));

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

    {

        scanf("%d",&a[i]);

        if(max < a[i])max = a[i];

    }

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

    {

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

        {

            int tmp = a[i] - a[j]>?a[i]-a[j]:a[j]-a[i];

            h[tmp]++;

        }

    }

    int res, flag =;

    for(int m=;m<=max+;m++)

    {

            int tk = k;

            int sum = ;

            flag = ;

            for(int i=m;i<=1e6;i+=m)

            {

                sum+=h[i];                        //剪枝操作

                if(sum>k*(k+)/)break;

            }

            if(sum>k*(k+)/)continue;

            res = m;

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

            {

                if(!re[a[i]%res])re[a[i]%res]++;

                else

                {

                    tk--;                        //这里不能直接把k给减了

                    if(tk<){flag =;break;}

                }

            }

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

            {

                re[a[i]%m]=;                    //注意每次都要清零，也可以用memset就是速度慢点

            }

            if(flag)break;

    }

    printf("%d\n",res);

}