首页 > ACM题库 > HDU-杭电 > hdu 2020 绝对值排序 -线性结构-[解题报告]C++
2013
12-26

hdu 2020 绝对值排序 -线性结构-[解题报告]C++

绝对值排序

问题描述 :

输入n(n<=100)个整数,按照绝对值从大到小排序后输出。题目保证对于每一个测试实例,所有的数的绝对值都不相等。

输入:

输入数据有多组,每组占一行,每行的第一个数字为n,接着是n个整数,n=0表示输入数据的结束,不做处理。

输出:

输入数据有多组,每组占一行,每行的第一个数字为n,接着是n个整数,n=0表示输入数据的结束,不做处理。

样例输入:

3 3 -4 2
4 0 1 2 -3
0

样例输出:

-4 3 2
-3 2 1 0

 这个题本来没必要贴出来,但发现了qsort竟然还可以对结构排序啊

说到底还是对qsort()的原理不清楚,只知道用。最近烦心事也一大堆,不想深究,以后有状态了再说吧。

下面是代码,开始用qsort直接排一个int,结果当然乱套,后来改为2*sizeof(int),奇迹出现了。。

这东西很高端啊。

/**
 * Author: Gneveek
 * Data: 2011-10-9
 * Descripition:  hdu - 2020
 */ 
#include <stdio.h>
#include <stdlib.h>

struct a{
	int x;
	int y;
};

int int_cmp(const void *a, const void *b)
{
	return *(int *)b - *(int *)a;
}

int main()
{
	//freopen("C:\\in.txt","r",stdin);
	struct a data[105];
	int n,i;
	while(scanf("%d",&n), n != 0)
	{
		for(i=0; i<n; i++)
		{
			scanf("%d",&data[i].x);
			if(data[i].x < 0)
			{
				data[i].y = 1;
				data[i].x = -data[i].x;
			}				
			else
				data[i].y = 0;
		}
		qsort(data,n,2*sizeof(int),int_cmp);
		
		for(i=0; i<n; i++)
		{
			if(data[i].y == 1)
			{
				if(i == n-1)
					printf("-%d",data[i].x);
				else
					printf("-%d ",data[i].x);
			}				
			else
			{
				if(i == n-1)
					printf("%d",data[i].x);
				else
					printf("%d ",data[i].x);
			}
				
		}
		putchar('\n');
	}
	return 0;
}

 

解题转自:http://blog.csdn.net/gneveek/article/details/6857242


  1. int half(int *array,int len,int key)
    {
    int l=0,r=len;
    while(l<r)
    {
    int m=(l+r)>>1;
    if(key>array )l=m+1;
    else if(key<array )r=m;
    else return m;
    }
    return -1;
    }
    这种就能避免一些Bug
    l,m,r
    左边是l,m;右边就是m+1,r;

  2. 这道题目的核心一句话是:取还是不取。
    如果当前取,则index+1作为参数。如果当前不取,则任用index作为参数。