题解 P1459 【三值的排序 Sorting a Three-Valued Sequence】

米奇奇米 · 2019-02-10 16:04:21 · 题解

#include<bits/stdc++.h>
using namespace std;
int a[100001],b[100001],n;
int ans;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        b[i]=a[i];//记录下原序列
    }
    sort(a+1,a+n+1);//快排，排序原序列
    for(int i=1;i<=n;i++)
    {
        if(a[i]!=b[i])
        ans++;//累加不同的数
    }
    if(ans%2!=0) cout<<(ans/2)+1<<endl;
       else cout<<ans/2<<endl;//再按照奇、偶性讨论即可
    return 0;
}

     将原序列由大到小进行排序，然后对照原序列找出不一样的数据，千万要记住要将不同的数量/2（分奇数、偶数讨论情况即可）。