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 条评论
登录 后参与评论

相关文章

来自专栏desperate633

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

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

872
来自专栏靠谱PM

JavaScript基本语法(三)

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

602
来自专栏web前端-

JS函数

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

792
来自专栏黑泽君的专栏

java语言反射的概述以及三种获取字节码文件对应的Class类型的对象的方式

反射的概述:   JAVA反射机制是在运行状态中,   对于任意一个类,都能够知道这个类的所有属性和方法(动态获取的信息);   对于任意一个对象,...

2643
来自专栏Linux驱动

指针学习(详解)

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

1715
来自专栏杨熹的专栏

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

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

3636
来自专栏一个爱吃西瓜的程序员

Python基础学习-字典

一:使用字典:在Python中,字典是一系列键-值对,与键相关联的值可以是数字、字符串、列表乃至字典。字典用放在花括号{}中的一系列键-值对表示。键与值之间用冒...

3589
来自专栏程序员互动联盟

【编程基础】C语言逻辑运算符

C语言关系运算符和逻辑运算符几乎无所不在,比如在循环语句、分支语句、逻辑判断等语句块中都会出现。学好这部分对学好C语言具有重要作用。 C语言中有一共有如下6中...

3686
来自专栏抠抠空间

re模块(正则表达式)

一、什么是正则表达式 正则就是用一些具有特殊含义的符号组合到一起(称为正则表达式)来描述字符或者字符串的方法。或者说:正则就是用来描述一类事物的规则。(在Pyt...

3096
来自专栏null的专栏

C/C++——set的基本操作总结

set容器中只能存储键,是单纯的键的集合,其中键是不能重复的。 set支持大部分的map的操作,但是set不支持下标的操作,而且没有定义mapped_type...

3073

扫码关注云+社区