首页 > ACM题库 > HDU-杭电 > HDU 2761-HOJ-Extended Normal Order Sort[解题报告]C++
2014
02-14

HDU 2761-HOJ-Extended Normal Order Sort[解题报告]C++

Extended Normal Order Sort

问题描述 :

When sorted in standard order, strings with digits in them may not sort to where they are expected. For instance, xyz100 precedes xyz2. In some applications such as listing files, normal order sort may be used where any string of digits in a character string is treated as a single digit with numerical value given by the digit string. For example, the following are in normal order:

XYZ001, XYZ2, XYZ003, XYZ08, XYZ23, XYZ100, XYZQ

We wish to extend normal order sort in two ways:

1. Lower case and upper case letters sort the same (with the upper case value).

2. If a plus (+) or minus (-) sign precedes a digit and does not follow a digit, it is considered part of the following number for sorting purposes.

So 123+456+7890 are three numbers separated by plus signs but A+003 is the same as A3.

To do our sort, we will use a library sort routine but we need to furnish a comparison routine. Write a comparison routine which takes as input two strings of printable, non-space ASCII characters (chr(33)-chr(126)) and returns:

-1 if the first string should precede the second in extended normal order
0 it the two strings are the same in extended normal order, or
1 if the first string should follow the second in extended normal order.

输入:

The first line of input contains a single integer N, (1 ≤ N ≤ 1000) which is the number of data sets that follow. Each data set consists of a single line of input containing the two strings to be compared separated by a space.

输出:

The first line of input contains a single integer N, (1 ≤ N ≤ 1000) which is the number of data sets that follow. Each data set consists of a single line of input containing the two strings to be compared separated by a space.

样例输入:

5
x-3 X0001
123-456-7890 123+456+7890
xYz000123J XyZ+123j
#$%^&*[]- abcdefgh
Abc47jKL+00123 ABC+47jkL123

样例输出:

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

http://acm.hit.edu.cn/hoj/problem/view?id=2761
多写几项 可以写出g(n)的通项
gn=2^n+(-1)^(n+1)
位数可以使用log10 (-1)对位数没有影响

#include <stdio.h>
#include <math.h>

int main()
{
    long long n,gn,dig;

    while (scanf("%lld", &n) == 1)
    {
        if (n == 0)
            printf("%d\n", 0);
        else
        {
            /*gn = pow(2, n)+pow(-1, n+1);*/
            dig = ceil(n*log10(2));
            printf("%lld\n", dig);
        }
    }

    return 0;
}

 

解题参考:http://blog.csdn.net/epk_lee/article/details/8203322


  1. bottes vernies blanches

    I appreciate the efforts you men and women place in to share blogs on such sort of matters, it was certainly useful. Keep Posting!

  2. 您没有考虑 树的根节点是负数的情况, 若树的根节点是个很大的负数,那么就要考虑过不过另外一边子树了

  3. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。

  4. 题目需要求解的是最小值,而且没有考虑可能存在环,比如
    0 0 0 0 0
    1 1 1 1 0
    1 0 0 0 0
    1 0 1 0 1
    1 0 0 0 0
    会陷入死循环

  5. “再把所有不和该节点相邻的节点着相同的颜色”,程序中没有进行不和该节点相邻的其他节点是否相邻进行判断。再说求出来的也不一样是颜色数最少的