UC知道求个程序
来源：百度知道 编辑：UC知道 时间：2024/06/22 08:22:25
Sort
Submit: 3 Accepted:0
Time Limit: 1000MS Memory Limit: 65536K
Description
Give you a sequence of N numbers. The goal is to move the numbers around so that at the end the sequence is ordered. The only operation allowed is to swap two adjacent numbers. Let us try an example:
Start with: 1 4 3 2
swap (1 4) 4 1 3 2
swap (3 2) 4 1 2 3
swap (1 2) 4 2 1 3
swap (4 2) 2 4 1 3
swap (1 4) 2 1 4 3
swap (4 3) 2 1 3 4
swap (2 1) 1 2 3 4
So the sequence (1 4 3 2) can be sorted with seven swaps of adjacent numbers. However, it is even possible to sort it with such swaps:
Start with: 1 4 3 2
swap (4 3) 1 3 4 2
swap (4 2) 1 3 2 4
swap (3 2) 1 2 3 4
The question is: What is the minimum number of swaps of adjacent numbers to sort a given sequence?
Input
In the first line you are given a integer N(1 <= N <= 50000), the length of the sequence, the second line followed by the N e
Submit: 3 Accepted:0
Time Limit: 1000MS Memory Limit: 65536K
Description
Give you a sequence of N numbers. The goal is to move the numbers around so that at the end the sequence is ordered. The only operation allowed is to swap two adjacent numbers. Let us try an example:
Start with: 1 4 3 2
swap (1 4) 4 1 3 2
swap (3 2) 4 1 2 3
swap (1 2) 4 2 1 3
swap (4 2) 2 4 1 3
swap (1 4) 2 1 4 3
swap (4 3) 2 1 3 4
swap (2 1) 1 2 3 4
So the sequence (1 4 3 2) can be sorted with seven swaps of adjacent numbers. However, it is even possible to sort it with such swaps:
Start with: 1 4 3 2
swap (4 3) 1 3 4 2
swap (4 2) 1 3 2 4
swap (3 2) 1 2 3 4
The question is: What is the minimum number of swaps of adjacent numbers to sort a given sequence?
Input
In the first line you are given a integer N(1 <= N <= 50000), the length of the sequence, the second line followed by the N e
其实就是一道冒泡排序题，算交换的次数的，下面是我写的代码，你按题目的要求试试。
#include <stdio.h>
void bubble(int *b, int n)
{
for(int i = 0; i<n; i++)
{
scanf("%d", &b[i]);
}
int temp, m, d = 0;
for(int j=1; j<=n; j++)
{
m = 0;
for(int i=0; i<n-j; i++)
{
if(b[i] > b[i+1])
{
temp = b[i];
b[i] = b[i+1];
b[i+1] = temp;
m++;
d++;
}
}
if(m == 0)
break;
}
printf("Output\n");
printf("%d\n", d);
}
void main()
{
int n;
printf("Input\n");
scanf("%d", &n);
int *s;
s = new int[n];
bubble(s, n);
}
好难啊!小斌 是离散编成题吗????