CF2009E-Klee's SUPER DUPER LARGE Array!!!
题目大意
给你一个长度为 \(n\) 的序列，包含 \([k,k+1,…,k+n-1]\) 。你可以从中挑选一个下标 \(i\) ，使得 \(x=|a_1+a_2+……+a_i-a_{i+1}-……-a_n]|\) 最小化。求可能的最小值。
题解
先不考虑绝对值，那最小的值一定出现在 最小的正数 和 最大的负数 之间，所以我们要找到这个边界。可以考虑进行二分查找。
#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define umap unordered_map
#define pq(x) priority_queue<x>
#define ppq(x) priority_queue<x,vector<x>,greater<x>>
#define endl '\n'
using namespace std;
using i128 = __int128;
const int mod =1e9+7;
template <typename T>void read(T&x){x=0;int f = 1;char c=getchar();for(;!isdigit(c);c=getchar())if(c=='-')f=-1;for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);x*=f;
}
template <typename T>void print(T x) {if (x < 0) { putchar('-'); x = -x; }if (x > 9) print(x / 10);putchar(x % 10 + '0');
}
#define int long long
const int N=5e5+5;
const int M=2e6+5;
inline void solve()
{int n,m;cin>>n>>m;int l=m,r=n+m-1; while(l<r){int mid=l+r>>1;if((m+mid)*(mid-m+1)/2-(mid+1+n+m-1)*(n+m-1-mid)/2>=0){r=mid;}else{l=mid+1;}}int ans1=(m+l)*(l-m+1)/2-(l+1+n+m-1)*(n+m-1-l)/2;int ans2=(m+l-1)*(l-1-m+1)/2-(l+n+m-1)*(n+m-l)/2;cout<<min(abs(ans1),abs(ans2))<<endl;
}signed main()
{ios;int T=1;cin>>T;for(;T--;) solve();return 0;
}