链接：https://codeforces.com/problemset/problem/1244/E
题意：长度为n的序列，k次操作，每次可将任意一个数加一或减一，问k次操作后 最小的 最大值和最小值的差是多少
题解：很明显，序列在向中间收缩， 答案满足单调性，可二分答案，分别暴力枚举最大值和最小值，查询上下界，判断是否能在k次内完成。复杂度nlogn*logn
#include <bits/stdc++.h> #define IO_read ios::sync_with_stdio(false);cin.tie(0) #define fre freopen("in.txt", "r", stdin) #define _for(i,a,b) for(int i=a; i< b; i++) #define _rep(i,a,b) for(int i=a; i<=b; i++) #define lowbit(a) ((a)&-(a)) using namespace std; typedef long long ll; template <class T> void read(T &x) { char c; bool op=0; while(c=getchar(), c<‘0‘||c>‘9‘) if(c==‘-‘) op=1; x=c-‘0‘; while(c=getchar(), c>=‘0‘&&c<=‘9‘) x=x*10+c-‘0‘; if(op) x=-x; } template <class T> void write(T x) { if(x<0) putchar(‘-‘), x=-x; if(x>=10) write(x/10); putchar(‘0‘+x%10); } const int maxn=1e5+5; int n; int a[maxn]; ll k, sum[maxn]; bool check(int val) { bool ok=false; for(int i=1; i<=n; i++) { int low=i; int high=lower_bound(a+1, a+1+n, a[i]+val)-a; ll area=1ll*low*a[low]-sum[low]+sum[n]-sum[high-1]-1ll*(n-high+1)*(a[low]+val); //printf("! val=%d, low=%d, high=%d, area=%I64d\n", val, low, high, area); if(area<=k) ok=true; } if(ok) return ok; for(int i=1; i<=n; i++) { int low=lower_bound(a+1, a+1+n, a[i]-val)-a-1; //注意这里要减去1 int high=i; ll area=1ll*low*(a[high]-val)-sum[low]+sum[n]-sum[high-1]-1ll*(n-high+1)*a[high]; //printf("! val=%d, low=%d, high=%d, area=%I64d\n", val, low, high, area); if(area<=k) ok=true; } return ok; } int main() { IO_read; //fre; cin>>n>>k; for(int i=1; i<=n; i++) cin>>a[i]; sort(a+1, a+1+n); for(int i=1; i<=n; i++) sum[i]=sum[i-1]+a[i]; int l=0, r=a[n]-a[1]; while(l<r) { int mid=l+r>>1; if(check(mid)) r=mid; else l=mid+1; //printf("! l=%d, r=%d, mid=%d\n", l, r, mid); } cout<<l<<"\n"; }
Codeforces 1244E Minimizing Difference （二分答案）
原文：https://www.cnblogs.com/Yokel062/p/11748490.html