如果考场上这题我做出来了,那么我就可以把bx2k推下去自己拿APIO的Au了......

感谢bx2k提供的算法....

后面那70分,我们可以观察

把它分成n-1块,每块内进行处理瞎搞搞...

具体来说就是每块内不可能是答案,所以只要套出所有的值就可以把所有答案算出来了

*因为答案至少是(ma-mi)/(n-1)

Update : 考虑到代码被waltz给Hack掉了....我补了一句话...

Update * : 考虑到代码又被waltz给Hack掉了....我又补了一句...

Update ** : 考虑到代码第三次被waltz给Hack掉了....我报警了...

第一版:

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include"gap.h"
#include<math.h>
#include<string>
#include<time.h>
#include<bitset>
#include<vector>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<fstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
long long a[100005];
long long findGap(int t,int n)
{
    if (t==1)
    {
        int i;
        long long l=-1,r=1000000000000000001ll;
        for (i=0;i+i<n;i++)
        {
            MinMax(l+1,r-1,&a[i],&a[n-i-1]);
            l=a[i];
            r=a[n-i-1];
        }
        long long ma=0;
        for (i=0;i<n-1;i++)
        {
            ma=max(ma,a[i+1]-a[i]);
        }
        return ma;
    }
    else
    {
        int i;
        long long mi,ma;
        MinMax(0,1000000000000000000ll,&mi,&ma);
        long long last=mi;
        long long ans=(ma-mi-2)/(n-1);
        int sum=0;
        for (i=1;i<n;i++)
        {
            long long tmi,tma;
            int temp=((ma-mi-2)%(n-1)*(i-1))/(n-1);
            MinMax(mi+1+(ma-mi-2)/(n-1)*(i-1)+sum,(mi+1+(ma-mi-2)/(n-1)*i)+temp,&tmi,&tma);
            sum=temp+1;
            if (tmi==-1) continue;
            ans=max(ans,tmi-last);
            last=tma;
        }
        ans=max(ans,ma-last);
        return ans;
    }
    return 0;
}