2.1.3 Sorting a Three-Valued Sequence 三值的排序

2.1.3 Sorting a Three-Valued Sequence 三值的排序

时间: 1ms        内存:64M

描述:

排序是一种很频繁的计算任务。现在考虑最多只有三值的排序问题。一个实际的例子是,当我们给某项竞赛的优胜者按金银铜牌序的时候。

在这个任务中可能的值只有三种1,2和3。我们用交换的方法把他排成升序的。

写一个程序计算出,给定的一个1,2,3组成的数字序列,排成升序所需的最少交换次数。

输入:

Line 1:
N (1 <= N <= 1000) Lines 2-N+1: 每行一个数字,共N行。(1..3)

输出:

共一行,一个数字。表示排成升序所需的最少交换次数。

示例输入:

9
2
2
1
3
3
3
2
3
1

示例输出:

4

提示:

参考答案(内存最优[752]):

#include<stdio.h>
#define MAX 1002
int a[MAX],b[4]={0},c[4]={0};
int n;
int main()
{
	int i,j,count;
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
		b[a[i]]++;
	}
	for (i=0;i<b[1]+b[2];i++){
        if (a[i]==3) c[3]++;
        else if (a[i]==2&&i<b[1]) c[1]++;
        else if (a[i]==1&&i>=b[1]) c[2]++;
        }
	printf("%d\n",c[3]+(c[1]>c[2]?c[1]:c[2]));
	return 0;
}

参考答案(时间最优[0]):

/*
ID: ayludon3
PROG: sort3
LANG: C++
*/
#include <fstream>
#include <iostream>
#include <string.h>
#include <math.h>
using namespace std;

int abs(int a)
{
    if(a>0)
        return a;
    else
        return (-1*a);

}
int main()
{
//    ifstream cin("sort3.in");
//    ofstream cout("sort3.out");
    int n,i,res;
    int p[1005],num[4],wrong[4];
    cin>>n;
    res=0;
    memset(num,0,sizeof(num));
    memset(wrong,0,sizeof(wrong));
    for(i=1;i<=n;i++)
    {
        cin>>p[i];
        num[p[i]]++;
    }
    //wrong[3]=C31+C32(3放在1、2位置上的个数)
    //wrong[2]=B21(2放在1位置上的个数)
    //wrong[1]=A12(1放在2位置上的个数)
    for(i=1;i<=num[1]+num[2];i++)
    {
        if(p[i]==3)
            wrong[3]++;
        else if(p[i]==2&&i<=num[1])
            wrong[2]++;
            else if(p[i]==1&&i>num[1])
                wrong[1]++;
    }
    //3放在1、2位置上的全部调走,另外加上A12和B12互换,再加上A12和B21的差
    //即res=wrong[3]+min(wrong[1],wrong[2])+abs(wrong[1]-wrong[2])=wrong[3]+max(wrong[1],wrong[2])
    res=wrong[3]+min(wrong[1],wrong[2])+abs(wrong[1]-wrong[2]);
    cout<<res<<endl;
    return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注