题解归档 - cf2187A

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

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

思路

A. Restricted Sorting

pattern

math_reasoning_search: exchange/adjacent-swap was suggested, but the useful invariant is the connected components of the value graph under allowed swaps.

claim

For a fixed k, build a graph on values/occurrences where two elements are adjacent if their value difference is at least k. Swaps generate arbitrary permutations inside each connected component, and cannot move an element across components.

Let mn=min(a), mx=max(a). If mx-mn>=k, all values with x-mn>=k or mx-x>=k are in one large component through mn/mx. Any value with both x-mn<k and mx-x<k is isolated from every other value.

Therefore sorting is possible iff every position whose value changes between a and sorted(a) uses only values in the large component.

necessary

If a mismatched position contains or needs a central isolated value v, then that value cannot be swapped with anything, so the component label at this position is fixed and sorting is impossible.

For every mismatched value v, we need

k <= max(v-mn, mx-v).

sufficient

If the above holds for all values appearing in mismatched positions, then every changed position belongs to the single large component. Values in that component can be permuted arbitrarily by swaps along a connected transposition graph, while fixed central values already match their sorted positions.

brute/check

Checked all arrays of length up to 7 over values 1..5 against an explicit component oracle, and also spot-checked BFS reachability on random small arrays.

edge

If the array is already sorted, zero operations sort it for every integer k, so there is no largest integer and the answer is -1.

代码

来源：problems/cf2187A/solution.cpp

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=200005;
ll s[maxn+5],a[maxn+5];
int main(){
    ll t,n,i,j,k,zc,pd,cur,dq,cnt,ans,mn,mx;
    scanf("%lld",&t);
    while(t--){
        scanf("%lld",&n);
        for(i=1;i<=n;i++){
            scanf("%lld",&s[i]);
            a[i]=s[i];
        }
        sort(a+1,a+n+1);
        pd=1;
        for(i=1;i<=n;i++){
            if(s[i]!=a[i]) pd=0;
        }
        if(pd){
            printf("-1\n");
            continue;
        }
        mn=a[1];
        mx=a[n];
        ans=1000000000000000000ll;
        for(i=1;i<=n;i++){
            if(s[i]!=a[i]){
                ans=min(ans,max(s[i]-mn,mx-s[i]));
                ans=min(ans,max(a[i]-mn,mx-a[i]));
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}