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

· · 题解

一篇很水的题解：

方法解释：找到它的原结果和目标结果，并作差：

原：2 3 1 1

目标：1 1 2 3

差：1 2 -1 -2

此时要交换两个数只需要对差进行改变，如将2和第一个1交换，2的差减1,1的差加1，就都变成0了，最后只需要把差全部变为0即可。

样例解释：

编号：1 2 3 4 5 6 7 8 9

原：2 2 1 3 3 3 2 3 1

目标：1 1 2 2 2 3 3 3 3 //因为要从小到大排

差：1 1 -1 1 1 0 -1 0 -2

将1和3对调，差变为0和0，将2和7对调，差变为0和0，将4和9对调，差变为0和-1，将5和9对调，差变为0和0，共4步。

因此，因尽量使它们‘差’的和尽量接近0，所以就有一种奇特的方法：

统计差为1的个数，这些ans都要+1的，再统计差为2的个数，如果有-2对应ans就+1，没有对应就+2。

下面上代码（在洛谷上过不了，所以别想抄题解，但把数据下下来发现答案都是正确的，在别的oj上也能过）：

#include<bits/stdc++.h>
#define f(i,a,b) for(register int i=a;i<=b;++i)
using namespace std;
int p,s,tot,ans,have,q,m;
char a[1005<<1],b;//会读入换行，数组大小要*2
int main()
{
    cin>>m;
    f(i,1,m<<1){//读入
        if(isdigit(b=getchar())){//判断是否为换行
            a[++p]=b;//存入
            if(b=='1'){//无需打排序，直接操作
                int k=a[++s]=='3';//判断是否为3，如果是3，则差为2
                ans+=a[s]=='2'+k;//先全部+1，再单独判断有没有对应
                have+=k;//统计差为2的个数
            }
            else tot+=b=='2';//统计2的个数
        } 
    }
    f(i,s+1,s+tot){//目标结果为2的部分
        ans+=a[i]=='3';//统计差为1的个数
    }
    f(i,s+tot+1,p){//目标结果为3的部分
        q+=a[i]=='1';//统计差为-2的个数
    }
    cout<<ans+((have>q)?have-q:0)<<endl;//把没有-2对应的2的部分加上
    return 0;
}

本人（蒟蒻）第一次发题解，但好像时间复杂度好像还蛮低的