一道简单的ACM题目,快速排序的,老是提交不成功,大家帮我看看
来源:学生作业帮 编辑:百度作业网作业帮 分类:综合作业 时间:2024/08/11 07:10:40
一道简单的ACM题目,快速排序的,老是提交不成功,大家帮我看看
Description
Give a set of numbers,output them after sort.You may use any algorithm you like to solve it.
Input
Each input file contains only one case.
Each test case begins with an integer N(0
Description
Give a set of numbers,output them after sort.You may use any algorithm you like to solve it.
Input
Each input file contains only one case.
Each test case begins with an integer N(0
![一道简单的ACM题目,快速排序的,老是提交不成功,大家帮我看看](/uploads/image/z/4170127-31-7.jpg?t=%E4%B8%80%E9%81%93%E7%AE%80%E5%8D%95%E7%9A%84ACM%E9%A2%98%E7%9B%AE%2C%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F%E7%9A%84%2C%E8%80%81%E6%98%AF%E6%8F%90%E4%BA%A4%E4%B8%8D%E6%88%90%E5%8A%9F%2C%E5%A4%A7%E5%AE%B6%E5%B8%AE%E6%88%91%E7%9C%8B%E7%9C%8B)
题目里面说的很清楚了,时间复杂度为n平方可能会超时,要用O(n*lgn)的算法才行.快速排序的时间复杂度在最坏情况下是 O(n2),
你用堆排序试试.下面是我写的堆排序的代码:
#include
#include
#define LEFT(i) (2*(i + 1) - 1)
#define RIGHT(i) (2* (i + 1))
void max_heapify_itr(int a[], int size, int index);
void build_max_heap(int a[], int size);
void heapsort(int a[], int size);
void exchg(int *a, int *b)
{
int tmp;
tmp = *a;
*a = *b;
*b = tmp;
}
void max_heapify(int a[], int size, int index)
{
int l, r, largest;
l = LEFT(index);
r = RIGHT(index);
if (l < size && a[l] > a[index]) {
largest = l;
} else {
largest = index;
}
if (r < size && a[r] > a[largest]) {
largest = r;
}
if (largest != index) {
exchg(&a[largest], &a[index]);
max_heapify(a, size, largest);
}
}
void max_heapify_itr(int a[], int size, int index)
{
int l, r, largest;
while (1) {
l = LEFT(index);
r = RIGHT(index);
if (l < size && a[l] > a[index]) {
largest = l;
} else {
largest = index;
}
if (r < size && a[r] > a[largest]) {
largest = r;
}
if (largest != index) {
exchg(&a[largest], &a[index]);
index = largest;
} else {
break;
}
}
}
void build_max_heap(int a[], int size)
{
int i;
for (i = size / 2; i >= 0; i--) {
max_heapify_itr(a, size, i);
}
}
void heapsort(int a[], int size)
{
int i;
build_max_heap(a, size);
for (i = 0; i < size; i++) {
exchg(&a[size - i - 1], &a[0]);
max_heapify_itr(a, size - i - 1, 0);
}
}
int main()
{
int N, i;
int *a;
scanf("%d", &N);
a = malloc(sizeof(int) * N);
for (i = 0; i < N; i++) {
scanf("%d", &a[i]);
}
heapsort(a, N);
for (i = 0; i < N; i++) {
printf("%d ", a[i]);
}
free(a);
return 0;
}
我在这个网上测了一下,这个代码结果如下:
Test # 1. Accepted
Use Time 4ms, Use Memory 36KB
Test # 2. Accepted
Use Time 0ms, Use Memory 36KB
Test # 3. Accepted
Use Time 8ms, Use Memory 36KB
Test # 4. Accepted
Use Time 0ms, Use Memory 40KB
Test # 5. Accepted
Use Time 0ms, Use Memory 36KB
Test # 6. Accepted
Use Time 4ms, Use Memory 44KB
Test # 7. Accepted
Use Time 0ms, Use Memory 40KB
Test # 8. Accepted
Use Time 0ms, Use Memory 40KB
Test # 9. Accepted
Use Time 8ms, Use Memory 56KB
Test #10. Accepted
Use Time 12ms, Use Memory 80KB
Test #11. Accepted
Use Time 88ms, Use Memory 432KB
Test #12. Accepted
Use Time 960ms, Use Memory 3948KB
Test #13. Accepted
Use Time 784ms, Use Memory 3944KB
Test #14. Accepted
Use Time 732ms, Use Memory 3944KB
Congratulation! Your solution has passed all of test cases.
Use Time 2600ms, Use Memory 3948KB
你用堆排序试试.下面是我写的堆排序的代码:
#include
#include
#define LEFT(i) (2*(i + 1) - 1)
#define RIGHT(i) (2* (i + 1))
void max_heapify_itr(int a[], int size, int index);
void build_max_heap(int a[], int size);
void heapsort(int a[], int size);
void exchg(int *a, int *b)
{
int tmp;
tmp = *a;
*a = *b;
*b = tmp;
}
void max_heapify(int a[], int size, int index)
{
int l, r, largest;
l = LEFT(index);
r = RIGHT(index);
if (l < size && a[l] > a[index]) {
largest = l;
} else {
largest = index;
}
if (r < size && a[r] > a[largest]) {
largest = r;
}
if (largest != index) {
exchg(&a[largest], &a[index]);
max_heapify(a, size, largest);
}
}
void max_heapify_itr(int a[], int size, int index)
{
int l, r, largest;
while (1) {
l = LEFT(index);
r = RIGHT(index);
if (l < size && a[l] > a[index]) {
largest = l;
} else {
largest = index;
}
if (r < size && a[r] > a[largest]) {
largest = r;
}
if (largest != index) {
exchg(&a[largest], &a[index]);
index = largest;
} else {
break;
}
}
}
void build_max_heap(int a[], int size)
{
int i;
for (i = size / 2; i >= 0; i--) {
max_heapify_itr(a, size, i);
}
}
void heapsort(int a[], int size)
{
int i;
build_max_heap(a, size);
for (i = 0; i < size; i++) {
exchg(&a[size - i - 1], &a[0]);
max_heapify_itr(a, size - i - 1, 0);
}
}
int main()
{
int N, i;
int *a;
scanf("%d", &N);
a = malloc(sizeof(int) * N);
for (i = 0; i < N; i++) {
scanf("%d", &a[i]);
}
heapsort(a, N);
for (i = 0; i < N; i++) {
printf("%d ", a[i]);
}
free(a);
return 0;
}
我在这个网上测了一下,这个代码结果如下:
Test # 1. Accepted
Use Time 4ms, Use Memory 36KB
Test # 2. Accepted
Use Time 0ms, Use Memory 36KB
Test # 3. Accepted
Use Time 8ms, Use Memory 36KB
Test # 4. Accepted
Use Time 0ms, Use Memory 40KB
Test # 5. Accepted
Use Time 0ms, Use Memory 36KB
Test # 6. Accepted
Use Time 4ms, Use Memory 44KB
Test # 7. Accepted
Use Time 0ms, Use Memory 40KB
Test # 8. Accepted
Use Time 0ms, Use Memory 40KB
Test # 9. Accepted
Use Time 8ms, Use Memory 56KB
Test #10. Accepted
Use Time 12ms, Use Memory 80KB
Test #11. Accepted
Use Time 88ms, Use Memory 432KB
Test #12. Accepted
Use Time 960ms, Use Memory 3948KB
Test #13. Accepted
Use Time 784ms, Use Memory 3944KB
Test #14. Accepted
Use Time 732ms, Use Memory 3944KB
Congratulation! Your solution has passed all of test cases.
Use Time 2600ms, Use Memory 3948KB
一道简单的ACM题目,快速排序的,老是提交不成功,大家帮我看看
ACM的一道题,看着很简单,提交却WA了,
一道简单的acm题,可是我老是通不过oj
一道很简单的ACM题,求大神看看我错在哪儿了,C++
北大ACM1001的题目,怎么提交都是wrong answer,帮我看看
一道杭电ACM的测试题,我运行的没问题,但是提交却是WA,
一道简单的acm题目中的一个bug求调试
问一道acm的题,提交时老实说超时.
ACM 的一道题提交总是Time Limit Exceeded,求救
一道简单的电路原理问题,高手帮我看看
求助一道ACM题一道很简单的ACM题目,题在这里我写的代码如下:#include using namespace std
CCNA网络工程师的一道题,大家帮我看看