第二场个人赛，打的不是很好，题被卡状态了(属实是排序思想基本功不过关了)，加上公共机不顺手（破DEV咋特么调代码），直接导致自己分析出来的数学I题没写完。。。

说完借口了，找找原因。在明确告诉我考试时的情况下依旧是将简单问题想复杂了，而且本期侧重讨论题目条件的边界问题处理，边界是这回的最困难的地方

TJ-S-1 半步相等

CF-1593D2和CF-1593D1

D1题面：

给定一个包含 （是偶数）个整数的数列 。

考虑一个可能的正整数 ，在每次操作中，你可以选定一个 ，并将 减少 。

你可以执行任意多次（也可能是零次）操作，使这个数列中的每一个数都相等。

请找出最大的符合条件的 ，如果 可以是任意的大小，输出 。

D2题面：

给定一个包含 （是偶数）个整数的数列 。

考虑一个可能的正整数 ，在每次操作中，你可以选定一个 ，并将 减少 。

你可以执行任意多次（也可能是零次）操作，使这个数列中至少一半的数相等。

请找出最大的符合条件的 ，如果 可以是任意的大小，输出 。

题目分析：

先说D1的。D1的想法并不难，因为你要求全部的都能缩成一样的。

首先最开始的时候没有仔细看题面，误以为第k次操作进行减k。

重新读了一遍题之后，很快注意到，如果要进行减操作的话，优先减大的，将大的减小。那么此时，如果要求全部相等，那么意味着这些所有的数字对于模数k同余。也就是说，经过很多次操作之后，大的数字必然能通过削减恢复成他们中的某一个更小的数字。

所以我们直接取标准为最小的数字，那么保证其他数字一定能和最小同余数。

那么，这些数字对于最小者的差的集合的最大公约数GCD就是答案。

想完了!

想完了？

寄喽（）

很遗憾，两发直接干碎了罚时。

接下来讨论这个做法会产生的边界问题。

首先是第一个问题，样例里面就有体现但是第一遍拍初稿的时候没有注意到，这个数可能是有重复的。

重复看似在这个题目里面没有啥大的处理必要，但是，两个数相同的时候他们的差为0，不需要和其他数字一起求最大公约数，因为0可以被其他任何的数字整除，最大公约数没有意义，gcd也在此时无法返回正确的结果。

关键字1 涉及到GCD的求解边界判0

毫无疑问，从小到大排序后，我们收集的是从第二个到最后一个的数差值的最大公约数。

for(int i=2;i<n;i++)
{
    ans=max(ans,gcd(a[i]-a[1],a[i+1]-a[1]));
}

但是第二个问题会出现，存在最大公约数的前提是 至少有两个数字

关键字2 GCD作用域需要至少有两个数，如果只有一个数字，没有最大公约数

所以，如果数据点只有两个，这个for循环根本就不会执行，此时不加以特殊处理的时候，相当于程序根本没有计算ans,直接就输出了初始值ans=1，这就是这两发寄掉的原因。得亏是自己造数据的时候恰巧造了一个只有两个数的数据，才发现。

怎么解决，加入一个Special Judge,如果只有两个数据点，直接返回二者的差值。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int gcd(int a,int b)
{
    return b==0?a:gcd(b,a%b);
}
int a[10001];
void solve()
{
    int n;
    cin>>n;
    map<int,int>mp;
    for(int i=1;i<=n;i++)cin>>a[i],mp[a[i]]=1;
    if(mp.size()==1)
    {
        cout<<-1<<endl;
        return;
    }
    sort(a+1,a+1+n);
    n=unique(a+1,a+1+n)-a-1;
    if(mp.size()==2)
    {
        cout<<a[2]-a[1]<<endl;
        return;
    } 
    int ans=1e12;
    for(int i=2;i<n;i++)
    ans=min(ans,gcd(a[i+1]-a[1],a[i]-a[1]));
    cout<<ans<<endl;
    return;
}
signed main()
{
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}

接着讨论D2的问题，显然，D2和D1思路一样，想要被设置成一样的部分的子数列最后都能被设置为该子序列初始时的最小值。

但是问题在于，的数据规模去暴力套跑D1显然是会炸掉的，这说明我们迫切的需要更换一种思维。

当时最开始想到的第一点就是，因为子序列都是必然修改成它的最小值的，所以我们枚举序列元素（sort好的有顺序）做子序列最小值端点，然后去找大小为可能的点集S，使得S内的所有点与最小值之差做最大公约数。

但是，点的选取又会造成暴力资源的浪费，显然，选择两个点凭空增加复杂度，不可取；而且其中存在大量无意义的点集选取。

显然，GCD的方法越来越走入死胡同，我们需要一个更彻底的方法。

走回来思考，我们D1为什么要使用GCD？

因为我们需要维护整个数列的所有元素与最小值之差是能被ans全部整除的，同时要保证ans最大，此时ans恰好为GCD。

那么，我们按顺序从最小值后面依次选择一个数A，与最小值作差，将这个差的所有因子全部找出来，然后拿着这个因子从A后面开始去找点，能整除的就加入点集合，看这个代表元素能够招来几个点构成一个可同时化归为相同数字的点集。 如果这个集合的大小严格不小于一半，那么这个因子就是一个最终ans的一个潜在的答案。

注意到，D1是由集合确定因子，而D2是有因子去碰集合。这表明由A求B，当A的状态过于难以确定的时候，尝试枚举B区证明存在A，进而证明B的重要性。

接下来思考边界问题的细节。

首先第一个问题，和上一个一样，重复元素。

社会重复元素不能直接map筛掉就不管了，以为涉及到点集的大小，压缩状态后无法正确的表示半数关系。所以 要用map存贮元素个数的信息 ，正好借此机会通过map存储的元素个数干掉了-1的情况

第二个问题，选择点的问题。

第一个选点是选择其作为最小值基准，这里是从1-n的，没有问题。

第二个选点是选择产生产生可能答案的因子生成器，也就是子序列的第二个数。 这个数会比基准大，如果基准值扫到最后一个，第二选点循环不会执行。由于扫到序列的最大值的时候，这个生成子序列大小必然为一。一般而言都会比一半小，结果不纳入考虑范围内，不会造成影响。

如果只有两个数据，那么已经被-1的情况筛掉了，此时已经满足有严格不小于一般的序列（长度为1）相等。

此时，子序列中已经有了个元素。(CF数据点2 WA)

第三次选点，选择比因子生成器大的数，用因子来判断该数据是否可用来加入点集。

如果数据生成器到了原序列末尾，第三个数不会再出现，那么点集合大小就为，那这个来比较就可以了，不会干涉答案产生。

至此，边界考虑清晰，正确性证明完毕。

最后一个关键点，因子的求解方法 可以在时间范围内求出来因子，但是需要注意，for循环模拟的i不会大于，这导致 漏掉了另一半因子(CF数据点1样例 WA)

所以对于每一个可以整除的i，需要两次因子判定。而且，1因子不用再算，凭空浪费时间复杂度。但是，i不能从2开始，因为des因子是1的对称因子，这个是需要进行计算的（1是所有数字的因数，但是1des=des，des可未必是其他数字的因子）(CF数据点1样例 WA)

for (int u = 1; u * u <= des; u++)
            {
                if (des % u == 0)
                {
                    t = mp[a[i]]+mp[a[j]];
                    if (u != 1)
                    {
                        for (int k = j + 1; k <= nn; k++)
                        {
                            if ((a[k] - mina) % u == 0)
                                t += mp[a[k]];
                            if (t >= (n + 1) / 2)
                                break;
                        }
                        if (t >= (n + 1) / 2)
                            ans = max(ans, u);
                    }

                    t = mp[a[i]]+mp[a[j]];
                    for (int k = j + 1; k <= nn; k++)
                    {
                        if ((a[k] - mina) % (des / u) == 0)
                            t += mp[a[k]];
                        if (t >= (n + 1) / 2)
                            break;
                    }
                    if (t >= (n + 1) / 2)
                        ans = max(ans, (des / u));
                }
            }

细节处理结束，

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1001;
int a[maxn];
void solve()
{
    int n;
    cin >> n;
    map<int, int> mp;
    bool tag = 1;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        mp[a[i]]++;
        if (mp[a[i]] >= (n + 1) / 2)
        {
            tag = 0;
        }
    }
    if (!tag)
    {
        cout << "-1" << endl;
        return;
    }
    sort(a + 1, a + 1 + n);
    int nn = unique(a + 1, a + 1 + n) - a - 1;
    int ans = 1;
    for (int i = 1; i <= nn; i++)
    {
        int mina = a[i];
        for (int j = i + 1; j <= nn; j++)
        {
            int t=mp[a[i]]+mp[a[j]];
            int des = a[j] - mina;
            for (int u = 1; u * u <= des; u++)
            {
                if (des % u == 0)
                {
                    t = mp[a[i]]+mp[a[j]];
                    if (u != 1)
                    {
                        for (int k = j + 1; k <= nn; k++)
                        {
                            if ((a[k] - mina) % u == 0)
                                t += mp[a[k]];
                            if (t >= (n + 1) / 2)
                                break;
                        }
                        if (t >= (n + 1) / 2)
                            ans = max(ans, u);
                    }

                    t = mp[a[i]]+mp[a[j]];
                    for (int k = j + 1; k <= nn; k++)
                    {
                        if ((a[k] - mina) % (des / u) == 0)
                            t += mp[a[k]];
                        if (t >= (n + 1) / 2)
                            break;
                    }
                    if (t >= (n + 1) / 2)
                        ans = max(ans, (des / u));
                }
            }
        }
    }
    cout << ans << endl;
    return;
}
signed main()
{
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}