题目大意

求出序列中前缀和后缀的最小差值即可

解题思路

可以推数学公式逃课（）

先把题目要你求最小值的式子：$∣a_1+a_2+...+a_x−(a_{x+1}+a_{x+2}+...+a_n)∣$化简一下。

代入每一项后，得到原式 =$|k+(k+1)+...+(k+x−1)−[(k+x)+(k+x+1)+...+(k+n−1)]|$

两段等差数列求和，得到原式 $ = ∣\frac{(k+k+x−1)\times x}{2}−\frac{(k+x+k+n−1)\times (n-x)}{2}| $

化简并整理，得到原式 $=| x^2+(2k-1)x-\frac {n(n+2k-1)}{2} |$。

令 $f(x)= x^2+(2k-1)x-\frac {n(n+2k-1)}{2}$

又因为 $n\leq2$，所以 $f(1)<0$,$f(n)>0$,则$f(1)\times f(n)<0$。综上可知 $f(x)=0$ 在区间 $[1,n]$ 内必定有且只有一个根。

令$f(x)=0$，利用求根公式解出方程的根。

设这个根为 $x$，则显然与 $0$ 最接近的两个函数值是 $f(⌊x⌋)$ 与 $f(⌊x⌋+1)$，取个绝对值找其中的较小值即可。

代码

void solve()
{
    int n,k;
    cin >> n >> k;

    int b=(2*k-1);
    int c=(n*(2*k+n-1)/2);
    double g=(1.0*b*b)+(4.0*c);
    double x=(1.0*sqrt(g)-1.0*b)/2.0;

    int nx=x;
    int y1=(int)abs(nx*nx+b*nx-n*(2*k+n-1)/2);
    int y2=(int)abs((nx+1)*(nx+1)+b*(nx+1)-n*  (2*k+n-1)/2);

    cout << min(y1,y2) <<endl;
}

时间复杂度

O(T).

（如果用二分做，那时间复杂度要再乘上一个 $log⁡n$。）