首页 > ACM题库 > HDU-杭电 > HDU 1862 EXCEL排序[解题报告] C++
2013
12-23

HDU 1862 EXCEL排序[解题报告] C++

EXCEL排序

问题描述 :

Excel可以对一组纪录按任意指定列排序。现请你编写程序实现类似功能。

输入:

测试输入包含若干测试用例。每个测试用例的第1行包含两个整数 N (<=100000) 和 C,其中 N 是纪录的条数,C 是指定排序的列号。以下有 N
行,每行包含一条学生纪录。每条学生纪录由学号(6位数字,同组测试中没有重复的学号)、姓名(不超过8位且不包含空格的字符串)、成绩(闭区间[0, 100]内的整数)组成,每个项目间用1个空格隔开。当读到 N=0 时,全部输入结束,相应的结果不要输出。

输出:

对每个测试用例,首先输出1行“Case i:”,其中 i 是测试用例的编号(从1开始)。随后在 N 行中输出按要求排序后的结果,即:当 C=1 时,按学号递增排序;当 C=2时,按姓名的非递减字典序排序;当 C=3
时,按成绩的非递减排序。当若干学生具有相同姓名或者相同成绩时,则按他们的学号递增排序。

样例输入:

3 1
000007 James 85
000010 Amy 90
000001 Zoe 60
4 2
000007 James 85
000010 Amy 90
000001 Zoe 60
000002 James 98
4 3
000007 James 85
000010 Amy 90
000001 Zoe 60
000002 James 90
0 0

样例输出:

Case 1:
000001 Zoe 60
000007 James 85
000010 Amy 90
Case 2:
000010 Amy 90
000002 James 98
000007 James 85
000001 Zoe 60
Case 3:
000001 Zoe 60
000007 James 85
000002 James 90
000010 Amy 90

http://acm.hdu.edu.cn/showproblem.php?pid=1862

简单的qsort二级排序

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

typedef struct _excel
{
    char no[7];
    char name[9];
    int score;
}excel;

excel ex[100001];

int cmpno(const void *a, const void *b)
{
    excel *fa = (excel*)a;
    excel *fb = (excel*)b;
    return strcmp(fa->no, fb->no) > 0 ? 1 : -1;
}

int cmpname(const void *a, const void *b)
{
    excel *fa = (excel *)a;
    excel *fb = (excel *)b;
    if(strcmp(fa->name, fb->name)!=0)return strcmp(fa->name, fb->name) > 0 ? 1 : -1;
    return strcmp(fa->no, fb->no) > 0 ? 1 : -1;
}

int cmpscore(const void *a, const void *b)
{
    excel *fa = (excel *)a;
    excel *fb = (excel *)b;
    if(fa->score != fb->score)return fa->score - fb->score > 0 ? 1 : -1;
    return strcmp(fa->no, fb->no) > 0 ? 1 : -1;
}

int main()
{
//    freopen("input.in", "r", stdin);
    int n, i, hw;
    int cas = 1;
    while(scanf("%d%d", &n, &hw)&&n){
        for(i = 0; i < n; i ++){
            scanf("%s%s%d", ex[i].no, ex[i].name, &ex[i].score);
        }
        if(hw == 1){
            qsort(ex, n, sizeof(ex[0]), cmpno);
        }
        else if(hw == 2){
            qsort(ex, n, sizeof(ex[0]), cmpname);
        }
        else if(hw == 3){
            qsort(ex, n, sizeof(ex[0]), cmpscore);
        }

        printf("Case %d:\n", cas ++);
        for(i = 0; i < n; i ++){
            printf("%s %s %d\n", ex[i].no, ex[i].name, ex[i].score);
        }
    }
    return 0;
}

解题报告转自:http://blog.csdn.net/wchyumo2009/article/details/7543544


  1. 不考虑最后将结果排序的话,快排的时间复杂度是O(N) ,而堆排的是O(N*logK),这样比较看,快排快

  2. for(int i=1; i<=m; i++){
    for(int j=1; j<=n; j++){
    dp = dp [j-1] + 1;
    if(s1.charAt(i-1) == s3.charAt(i+j-1))
    dp = dp[i-1] + 1;
    if(s2.charAt(j-1) == s3.charAt(i+j-1))
    dp = Math.max(dp [j - 1] + 1, dp );
    }
    }
    这里的代码似乎有点问题? dp(i)(j) = dp(i)(j-1) + 1;这个例子System.out.println(ils.isInterleave("aa","dbbca", "aadbbcb"));返回的应该是false