问题标题: 酷町堂：1553 购票排队　wa 10

Question

0

已解决

傅文彬

新手天翼

1553 购票排队

题目描述 Description

在某市即将举办一次巨星演唱会，由于购票人数太多，官方决定在某一时段在网上放出排号卡片，（假设一共放出排号卡10000张），然后购票人根据号码的先后在售票窗口买票，但是每个人到达售票窗口的顺序不同。此时只有一名工作人员对队伍进行重新排序，即每次只能根据两个人的号码调换相邻两个人的位置，请问要经过多少次调换才能把队伍按照号码顺序排好。

输入描述 Input Description

输入文件有两行数据，第一行是带着排号卡来排队买票的总数N（不大于10000），第二行是N个不同的数表示最初的排队顺序。

输出描述 Output Description

一个数据，是最少的调换次数。

样例输入 Sample Input

4
12 5 2 1

样例输出 Sample Output

6

WA Runtime Error:10分

#include<bits/stdc++.h>

using namespace std;

int n,a[1000],sum;

int main() {

cin>>n;

for(int i=1;i<=n;i++){

cin>>a[i]; }

for(int i=1;i<=n-1;i++){//当前比较的次数

for(int j=1;j<=n-i;j++){//比较的次数

if(a[j]>a[j+1]){ swap(a[j],a[j+1]); //从小到大排序 sum++; } } }

cout<<sum; return 0; }

Answer 1

已采纳

方晨顺

中级守护

冒泡排序要优化一下，代码如下

    for(int i=1;i<=n-1;i++)
    {
        flag=false;
        for(int j=1;j<=n-i;j++)
        {
            if(a[j]>a[j+1])
            {
                swap(a[j],a[j+1]);
                s++;
                flag=true;
            }
        }
        if(!flag)
            break;
    }

Answer 2

傅文彬

新手天翼

请问大家思路是啥，谢谢

Answer 3

黄子扬

新手守护

循环写错了

for(i=1;i<=n-1;i++)

for(j=i+1;j<=n;j++)

if(x[i]>x[j])

{

swap(x[i],x[j]);

num++;

}

Answer 4

黄依成

中级天翼

循环(int i=1;i<=n-1;i++)
    {
        循环(int j=1;j<=n-i;j++)
        {
            如果(a[j]>a[j+1])
            {
                交换(a[j],a[j+1]);
                cnt自加;
            }
        }
    }

数组定义：int n,a[10005],sum=0;

问题标题: 酷町堂：1553 购票排队 wa 10

4 个回答:

问题标题: 酷町堂：1553 购票排队　wa 10