Xtu 1150 Assembly Line

http://202.197.224.59/OnlineJudge2/index.php/Problem/read/id/1150

题意:任意多个ABC三个数,问最少交换多少个任意位置的两个数,能使字符窜有序

分析:记录ABC的个数,one two three,循环字符窜one的个数,若one中有B,则先从two中找是否含有A

         若含有则交换,若没有则找three中的A。同理若one中有C,则先找three中的A,若three中没有A,则找

         B中的A。

         找完one后,就找two

         当然这个很容易就能理解,当A中找到B,若在B中找到A,则ans最终+1,若B中没有A,则B和C中的A交换,

         在接下来找的过程中,two中的C会和C中B交换,这样ans等同于+2

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int MN=1100;

char data[MN];
int len;
int swap_times;

void swap(int i,int k)
{
    int tmp=data[i];
    data[i]=data[k];
    data[k]=tmp;
    swap_times++;
}

bool find(char s,int start,int end,int k)
{
    for(int i=start; i<end; i++)
    {
        if(s==data[i])
        {
            swap(i,k);
            return true;
        }
    }
    return false;
}

int main()
{
    int T,i,j;
    int one,two,three;
    bool flag;
    scanf("%d",&T);
    while(T--)
    {
        swap_times=0;
        scanf("%s",data);
        len=strlen(data);
        one=two=three=0;
        for(i=0; data[i]; i++)
        {
            if(data[i]=='A') one++;
            if(data[i]=='B') two++;
            if(data[i]=='C') three++;
        }
        for(i=0; i<one; i++)
        {
            if(data[i]=='B')
            {
                flag=find('A',one,one+two,i);
                if(!flag) find('A',one+two,one+two+three,i);
            }
            else if(data[i]=='C')
            {
                 flag=find('A',one+two,one+two+three,i);
                if(!flag) find('A',one,one+two,i);
            }
        }
        for(i=one; i<one+two; i++)
        {
            if(data[i]=='C')
                find('B',one+two,one+two+three,i);
        }
        printf("%d\n",swap_times);
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Linux驱动

指针学习(详解)

在指针中*是取内容,&是取地址 (在结构体中时:变量结构体用".",指针结构体用"->") 通常有两种的表示: 1. 通过指针向指向的地址内容赋值 *p=a;...

18850
来自专栏web前端-

JS函数

      function 函数名()       {         这里是要执行的代码      }

11420
来自专栏武军超python专栏

2018年9月9日正则表达式随堂记

*********************** 今天遇到的新单词: element n元素,要素 multibyte n多字节 sequence n数列...

13140
来自专栏算法与数据结构

栈与递归 实现 十进制转二进制

6-4 十进制转换二进制(15 分) 本题要求实现一个函数,将正整数n转换为二进制后输出。 函数接口定义: void dectobin( int n ); 函数...

32250
来自专栏desperate633

深入理解Java中静态初始化块

在Java中,有两种初始化块:静态初始化块和非静态初始化块。它们都是定义在类中,用大括号{}括起来,静态代码块在大括号外还要加上static关键字。

9720
来自专栏尾尾部落

[剑指offer] 把数组排成最小的数

输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组{3,32,321},则打印出这三个数字能排成的最小数字...

32720
来自专栏10km的专栏

javabean:boolean和Boolean类型的getter方法名是有区别的

javaBean中,要设置或获取某个property的值,就需要相应的get和set方法,对于primitive和自定义类类型的属性(如:property),g...

24890
来自专栏靠谱PM

JavaScript基本语法(三)

一、数组的概念: 所谓数组,就是将多个元素(通常是同一类型)按一定顺序排列放到一个集合中,那么这个集合我们就称之为数组。

7520
来自专栏杨熹的专栏

Day 1-Java-imooc-3.运算符

课程地址:http://www.imooc.com/learn/85 总结图片来自 http://www.imooc.com/article/10535 ? 本...

38760
来自专栏java初学

static关键字

308100

扫码关注云+社区

领取腾讯云代金券