列表

详情


CMB13. 鸡鸭分类问题

描述

农场有n只鸡鸭排为一个队伍,鸡用“C”表示,鸭用“D”表示。当鸡鸭挨着时会产生矛盾。需要对所排的队伍进行调整,使鸡鸭各在一边。每次调整只能让相邻的鸡和鸭交换位置,现在需要尽快完成队伍调整,你需要计算出最少需要调整多少次可以让上述情况最少。例如:CCDCC->CCCDC->CCCCD这样就能使之前的两处鸡鸭相邻变为一处鸡鸭相邻,需要调整队形两次。

输入描述

输入一个长度为N,且只包含C和D的非空字符串。

输出描述

使得最后仅有一对鸡鸭相邻,最少的交换次数

示例1

输入:

CCDCC

输出:

2

原站题解

C 解法, 执行用时: 1ms, 内存消耗: 372KB, 提交时间: 2020-08-25

#include<stdio.h>
int main(void)
{
    int i,num,left_num;
    char ch,first_char;
    num=0;
    left_num = 1;
    i=1;
    scanf("%c",&ch);
    first_char=ch;
    while(ch!='\n')
    {
        scanf("%c",&ch);
        i=i+1;
        if(ch==first_char)
        {
            left_num+=1;
            num = num+i-left_num;
        }
    }
    printf("%d",num);
    return 0;
}

C 解法, 执行用时: 1ms, 内存消耗: 376KB, 提交时间: 2019-11-03

#include <stdio.h>
#include<string.h>
 
int main(void)
{
    int i=0,j=0,num=0;
    char str[100],t;
    scanf("%s",str);
    int len=strlen(str);
    for(i=0;i<len;i++)
        for(j=i;j<len;j++)
        {
            if(str[i]>str[j])
            {
                t=str[i];
                str[i]=str[j];
                str[j]=t;
                num=num+j-i;
            }
        }
    printf("%d\n",num);
    return 0;
}

C 解法, 执行用时: 2ms, 内存消耗: 224KB, 提交时间: 2019-11-22

#include <stdio.h>
#define N 200
int main(){
    int i,n=0,j,s,t=0;
    char a[N]={0};
    scanf("%s",a);
    while(a[n])
        n++;
    for(i=0;i<n;i++)
        for(j=i;j<n;j++)
        {
            if(a[i]>a[j])
            {
                s=a[i];
                a[i]=a[j];
                a[j]=s;
                t=t+j-i;
            }
        }
    printf("%d",t);
}

C 解法, 执行用时: 2ms, 内存消耗: 264KB, 提交时间: 2019-07-18

#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#define MAX 100

int main()
{
    int i=0,j=0;
    char zz[MAX],s;
    scanf("%s",zz);
    int num=0;
    int len=strlen(zz);
//    printf("%d\r\n",len);
    for(i=0;i<len;i++)
        for(j=i;j<len;j++)
        {
            if(zz[i]>zz[j])
            {
                s=zz[i];
                zz[i]=zz[j];
                zz[j]=s;
                num=num+j-i;
            }
        }
    
    printf("%d\r\n",num);
    
    
    
    
    return 0;
}

C 解法, 执行用时: 2ms, 内存消耗: 312KB, 提交时间: 2021-10-31

#include <stdio.h>
#include <stdlib.h>

int main()
{
    char str[100];
    int t=0;
    char temp;
    int i=0, count=0;
    gets(str);
    while(str[i]!='\0')
    {
        if(str[i]!=str[i-1])
        {
            if(str[i]=='D')
                t=i;
            else
            {
                temp = str[i];
                str[i] = str[t];
                str[t] = temp;
                count += i-t;
                t++;
            }
        }
        i++;
    }
    printf("%d", count);
    return 0;
}

上一题