P1459 [USACO2.1]三值的排序 Sorting a Three-Valued Sequence
程序员文章站
2024-03-19 09:29:28
...
题目描述
给定一个长度为 N 的序列,序列中只包含 1,2,3 三种数字。
现在需要你将序列按升序进行排序,排序必须通过一系列的交换操作来完成。
交换操作是指将两个位置 p 和 q 上的元素进行互换。
请你求出将序列排成升序序列,最少需要进行多少次交换操作。
输入格式
第一行包含整数 N。
接下来 N 行,每行包含一个 1∼3 之间的整数,表示序列中的一个元素。
输出格式
共一行,包含一个整数,表示将序列排成升序需要的最少交换次数。
数据范围
1≤N≤1000
样例
输入样例:
9
2
2
1
3
3
3
2
3
1
输出样例:
4
算法1
(贪心)
这个题最后排完序一定是1112222333这样的形势,
在未排序之前可能是以下六种
1//2 1 3 …1
2//1 3 2 …1
3//1 2 3 …0
4//2 3 1 …2
5//3 1 2 …2
6//3 2 1 …1
我们发现第四种和第五种需要交换两次,而实际上我们可以交换最后两个将4,5变成1,6,这样再交换一次就可以了,我们知道每次交换最多可以让两个数归为,这样我们可以让2和3归为,然后后半段多余的2和3其实就是4和5的情况,然后我们再交换一次,最后我们统计第一段种非1的个数就可以了。
时间复杂度
参考文献
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int a[N];
int b[4];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
b[a[i]]++;
}
int s1=0,s2=0;
for(int i=b[1]+1;i<=n-b[3];i++) //第二段中3的个数
if(a[i]==3) s1++;
for(int i=n-b[3]+1;i<=n;i++) //第三段中2的个数
if(a[i]==2) s2++;
int num=max(s1,s2); //其实是min(s1,s2)+abs(s2-1),
for(int i=1;i<=b[1];i++) //非1的个数
if(a[i]!=1) num++;
cout<<num;
return 0;
}