牛客练习赛63c牛牛的揠苗助长，二分，货仓选址
牛牛的揠苗助长
https://ac.nowcoder.com/acm/contest/5531/C
（货仓选址问题）在数轴上选一点，使得该点到其他点的距离和最小
结论：选择该组数字的中位数即可，
结论：选择该组数字的中位数即可，
一共n个数，当n为奇数时，中位数【（n+1)/2】，当n为偶数时，a【（n+1)/2】~a【（n+1)/2+1】之内的数皆可
这个题目出现至少，八成就是二分
那么证明下天数是分成两段的
设第x天恰好（最少）满足要求，那么第x+1天，有一个苗增高导致不完美，那么我们可以用减一的办法让它恢复
这样x后面的天都可以变成腕足条件的
所以二分天数是可以的
那么证明下天数是分成两段的
设第x天恰好（最少）满足要求，那么第x+1天，有一个苗增高导致不完美，那么我们可以用减一的办法让它恢复
这样x后面的天都可以变成腕足条件的
所以二分天数是可以的
（这个应该是最短的正常c++代码）
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef long long ll;
ll n,l,r,mid,a[N],b[N];
bool ok(ll x){
for(int i=1;i<=n;i++){
b[i]=a[i]+x/n+(x%n>=i);
}
sort(b+1,b+1+n);
ll res=0;
for(int i=1;i<=n;i++) res+=abs(b[i]-b[(n+1)/2]);
return res<=x;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
l=1, r=1e14;
while(l<=r){
mid=(l+r)/2;
if(ok(mid)) r=mid-1;
else l=mid+1;
}
cout<<l;
return 0;
} 创作不易点个赞呗
Momenta公司福利 555人发布