题解归档 - cf2229A

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2229A
• 本地来源：problems/cf2229A/idea.md
• 题目链接：https://codeforces.com/contest/2229/problem/A
• 原始标题：cf2229A

思路

cf2229A

pattern: diameter shrink.

claim: The answer is ceil((max(a)-min(a))/2).

necessary: In one operation, the leftmost slime can move right by at most 1 and the rightmost slime can move left by at most 1, so the diameter decreases by at most 2.

sufficient: Repeatedly choose any integer between the current extremes, for example the midpoint. Then both extremes move toward each other whenever they differ, so after ceil(diameter/2) operations all slimes can meet.

brute/check: Simulate repeatedly choosing the midpoint on small arrays.

edge: Already equal gives 0; odd diameter rounds up.

代码

来源：problems/cf2229A/solution.cpp

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
    ll t,n,i,x,mn,mx;
    scanf("%lld",&t);
    while(t--){
        scanf("%lld",&n);
        mn=1000000000;
        mx=0;
        for(i=1;i<=n;i++){
            scanf("%lld",&x);
            mn=min(mn,x);
            mx=max(mx,x);
        }
        printf("%lld\n",(mx-mn+1)/2);
    }
    return 0;
}