湘潭大学 1150 Assembly Line ABC移动有关问题

湘潭大学 1150 Assembly Line ABC移动问题
Assembly LineAccepted : 80 Submit : 469Time Limit : 1000 MS Memory Limit : 65536 KB 
题目描述

胡大加工厂出产一种特殊零件。某天，客户到厂来查看零件。工厂生产的零件有三个质量等级从高到低分别为A、B、C，但是流水线上的零件质量参差不齐。为了给客户留下好的印象，胡大决定把流水线上的零件整理下，最前面既最左边为质量最高的A等级零件，接着为B、C等级的零件。胡大每次可以选择两个零件，互换其位置。为了节省体力，胡大想知道最少的互换次数。

输入

第一行是一个整数K，表示样例个数。 每组样例为一个字符串，由字符'A','B','C',组成，长度不超过1000个字符，表示零件的原始顺序。

输出

对于每组样例,输出一行，即最少的互换次数。

样例输入

2CBAABAC

样例输出

11

思路：
先对原字符串排序，得到最后需要的升序序列，对原字符串和结果字符串的对应字符进行比较，得到A-B,A-C,B-C,B-A,C-A,C-B,的个数，
 可以把一个串分为很多串
所有可能的对应结果  为 ：只有 1中字母  一次都不用交换A B CA B C如果只有2种字母  则肯定都是像上面的1次的交换  如：AB  AC BA  BC  CA CBBA  CA AB  CB  AC BC均需要1次交换如果有3中字母  则共有6种排序前ABC  ACB BAC BCA CAB CBA排序后ABC  ABC ABC ABC ABC ABC则对应第一种为0   第二种 第三种 第6中 由于有一个字母相同   相当于只有2中字母的  只需要1次交换  第4 5种  需要交换两次  我们可以用 处理完上面的2种情况后剩下的 A-C的个数表示BCA-ABC 这种情况的个数用A-B表示CAB-ABC情况的个数
具体代码如下：

#include<stdio.h>#include<string.h>#include <algorithm>#include<queue>using namespace std;const int maxn = 1000 + 5;int min(int a,int b){    return a>b?b:a;}int main(){    int k,b[7];    char s[maxn],a[maxn];    scanf("%d",&k);    while(k--)    {                scanf("%s",s);        int len=strlen(s),i,count,ret;        for(i=0;i<len;i++)            a[i]=s[i];        sort(s,s+len);        memset(b,0,sizeof(b));        for(i=0;i<len;i++)        {            if(s[i]=='A'&&a[i]=='B')            b[0]++;            if(s[i]=='A'&&a[i]=='C')            b[1]++;            if(s[i]=='B'&&a[i]=='C')            b[2]++;            if(s[i]=='B'&&a[i]=='A')            b[3]++;            if(s[i]=='C'&&a[i]=='A')            b[4]++;            if(s[i]=='C'&&a[i]=='B')            b[5]++;        }        count=0;            for(i=0;i<3;i++)        {            ret=min(b[i],b[i+3]);            count+=ret;            b[i]-=ret;b[i+3]-=ret;        }        for(i=0,ret=0;i<6;i++)        ret+=b[i];        printf("%d\n",count+b[0]*2+b[1]*2);    }    return 0;}

  

查看更多 下一篇