牛客練習試合63 C

l i n k link link
C牛の苗が助長する
标题:牛牛には1列の菜園があり、長さはn、i i i番目の菜園の料理の高さはa[i]a[i]a[i]である.i i日目はi i iブロックの高さが1増加し,n+1 n+1 n+1日目は1ブロックの高さが1増加し,一度に類推する.しかし、牛には1つの菜園の高さを1つ増やしたり、1を減らしたりする魔法があり、少なくとも何日ですべての菜園の高さを一致させることができますか.タイトル保証開始時、菜園の高さはバラバラだった.考え方:二分+中位数は、要求された問題を二分で判定的な問題に変換することができますが、x x x日をどのように判断すればいいのでしょうか.私たちはすべての高さを統一的な高さに変えることを知っていて、絶対的な高さとは関係なく、相対的な高さと関係があるので、私たちはまずどの位置の菜園の高さが相対的に増加したかを求めて、それから私たちは新しい配列を得て、私たちが要求しているのはこの配列のすべての要素を同じにするには少なくとも何日かかります.もしこの値がxより小さいならば、さもないとだめです.配列のすべての要素を同じにするのは中位数で解決できる問題です.では、この問題は書けます.c o d e code code:

#include 
#define ll long long
#define pi pair
#define mk make_pair
#define pb push_back
using namespace std;

const int maxn = 1e5+10;
int a[maxn];
int n;

bool ok(ll x)
{
	vector<ll>G;
	for(int i=1;i<=n;i++)G.pb(a[i] + (i <= x%n));
	sort(G.begin(),G.end());
	
	ll m = G[n/2],ans = 0;
	
	for(auto it : G)
	{
		ans += abs(it - m);
	}
	if(ans <= x)return true;
	else return false;
}
int main()
{
	
	cin >> n;
	for(int i=1;i<=n;i++)scanf("%d",a+i);
	ll l = 1,r = 1e14,ans = 0;

	while(l <= r)
	{
		int mid = (l+r)/2;
		if(ok(mid))r = mid - 1,ans = mid;
		else l = mid + 1;
	}
	printf("%lld
",ans);
	return 0;
}