题目大意

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

解题思路

可以推数学公式逃课（）

先把题目要你求最小值的式子：$∣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$。）

写了个开区间二分，感觉在需要函数二分时比较好理解

#include <bits/stdc++.h>
using namespace std;
#define int long long
int t, n, k, sum;

void solve() {
    cin >> n >> k;
    int l = max(-1ll, n / 2 - 1), r = n;
    const int sum = (2 * k + n - 1) * n / 2;
    auto f = [&](int m) {
        return (2 * k + m) * (m + 1) - sum;
    };
    while (r - l > 1) {
        int mid = l + (r - l) / 2;
        if (f(mid) < 0) {
            l = mid;
        } else if (f(mid) > 0) {
            r = mid;
        } else {
            break;
        }
    }
    l = max(0ll, l), r = min(r, n - 1);
    cout << min(abs(f(l)), abs(f(r))) << '\n';
}

signed main() {
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

二分答案

令 $a_1+...+a_i$为$sum1$,$a_i+1+...a_n$为$sum2$,很明显题解是求min(|sum1-sum2|). 根据i的增大，sum1-sum2很明显具有单调性，二分$sum2 \le sum1$的位置，再让当前位置减一则是$sum1 \le sum2$的位置，分别求出两个位置的答案，求最小值即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long 
int a[200005];
int jc[200005];
const int mod =1e9+7;
int l1,r1;
bool check(int x)//判断
{
  int sum1=(x-l1+1)*(l1+x)/2;//等差数列求和
  int sum2=(r1-x)*(r1+x+1)/2;
  if(sum1>=sum2)
  {
    return 1;
  }
  else
  return 0;
}
signed main()
{
  int t;
  cin >> t;
  while(t--)
  {
    int o,p;
    cin >> o >> p;
    l1=p,r1=p+o-1;
    int l=l1,r=r1;
    while(l<=r)//二分
    {
     int mid=(l+r)/2;
     if(check(mid))
     {
       r=mid-1;
     }
     else
     l=mid+1;
    } 
  r=r+1;
  int sum1=(r-l1+1)*(l1+r)/2;
  int sum2=(r1-r)*(r1+r+1)/2;
  int ans=0;
  ans=abs(sum1-sum2);
  r--;
  sum1=(r-l1+1)*(l1+r)/2;
  sum2=(r1-r)*(r1+r+1)/2;
  ans=min(ans,abs(sum1-sum2));
    cout <<ans<<'\n';
  }
}