{"id":443,"date":"2013-07-26T16:45:37","date_gmt":"2013-07-26T08:45:37","guid":{"rendered":"http:\/\/blog.dayandcarrot.net\/?p=443"},"modified":"2013-07-26T16:45:37","modified_gmt":"2013-07-26T08:45:37","slug":"1028-list-sorting-25-stl%e4%b8%ad%e8%87%aa%e5%ae%9a%e4%b9%89%e6%8e%92%e5%ba%8f","status":"publish","type":"post","link":"https:\/\/dayandcarrot.space\/?p=443","title":{"rendered":"1028. List Sorting (25) | STL\u4e2d\u81ea\u5b9a\u4e49\u6392\u5e8f"},"content":{"rendered":"

\u65f6\u95f4\u9650\u5236<\/span><\/h1>\n
\n
\n
200 ms<\/div>\n<\/div>\n
\n
\u5185\u5b58\u9650\u5236<\/div>\n
32000 kB<\/div>\n<\/div>\n
\n
\u4ee3\u7801\u957f\u5ea6\u9650\u5236<\/div>\n
16000 B<\/div>\n<\/div>\n
<\/div>\n
<\/div>\n<\/div>\n
\nExcel can sort records according to any column. Now you are supposed to imitate this function.
\nInput<\/b>
\nEach input file contains one test case. For each case, the first line contains two integers N (<=100000) and C, where N is the number of records and C is the column that you are supposed to sort the records with. Then N lines follow, each contains a record of a student. A student’s record consists of his or her distinct ID (a 6-digit number), name (a string with no more than 8 characters without space), and grade (an integer between 0 and 100, inclusive).
\nOutput<\/b>
\nFor each test case, output the sorting result in N lines. That is, if C = 1 then the records must be sorted in increasing order according to ID’s; if C = 2 then the records must be sorted in non-decreasing order according to names; and if C = 3 then the records must be sorted in non-decreasing order according to grades. If there are several students who have the same name or grade, they must be sorted according to their ID’s in increasing order.
\nSample Input 1<\/b><\/p>\n
3 1\n000007 James 85\n000010 Amy 90\n000001 Zoe 60<\/pre>\n
Sample Output 1<\/b><\/p>\n
000001 Zoe 60\n000007 James 85\n000010 Amy 90<\/pre>\n
Sample Input 2<\/b><\/p>\n
4 2\n000007 James 85\n000010 Amy 90\n000001 Zoe 60\n000002 James 98<\/pre>\n
Sample Output 2<\/b><\/p>\n
000010 Amy 90\n000002 James 98\n000007 James 85\n000001 Zoe 60<\/pre>\n
Sample Input 3<\/b><\/p>\n
4 3\n000007 James 85\n000010 Amy 90\n000001 Zoe 60\n000002 James 90<\/pre>\n
Sample Output 3<\/b><\/p>\n
000001 Zoe 60\n000007 James 85\n000002 James 90\n000010 Amy 90<\/pre>\n<\/div>\n
============================================
\n\u8fd9\u4e2a\u9898\u76ee\u80fd\u60f3\u5230\u6700\u597d\u7684\u529e\u6cd5\uff0c\u5c31\u662f\u7528set\u7136\u540e\u91cd\u8f7d\u4e00\u4e2a\u81ea\u5b9a\u4e49\u6392\u5e8f\u4e86 \u611f\u8c22\u90ed\u5609\uff0c\u611f\u8c22STL\uff01
\nset\u8fd9\u4e2a\u4e1c\u897f\u561b\uff0c\u597d\u50cf\u662f\u7528\u7ea2\u9ed1\u6811\u8fd8\u662f\u4ec0\u4e48\u5b9e\u73b0\u7684(\u5370\u8c61\u4e2d\u662f\u8fd9\u6837\u7684) \u539f\u6765\u6253\u7b97\u7528vector\u7684\uff0c\u4f46\u662fvector\u597d\u50cf\u4e0d\u80fd\u5728\u63d2\u5165\u7684\u65f6\u5019\u5c31\u6839\u636e\u81ea\u5b9a\u4e49\u7684\u6392\u5e8f\u65b9\u6cd5\u6392\u5e8f\u597d\u63d2\u8fdb\u53bb\uff0c\u8fd9\u6837\u5982\u679c\u5168\u90e8\u5f55\u5165\u5b8c\u4e86\u6574\u4f53\u6392\u5e8f\u4e00\u904d\u662f\u4e0d\u662f\u66f4\u8017\u8d39\u65f6\u95f4\u5462\uff1f
\n\u53c2\u8003\u6587\u7ae0\uff1a
\nhttp:\/\/blog.csdn.net\/stone_sky\/article\/details\/8471722 \u8bb2\u7684\u662f\u81ea\u5b9a\u4e49\u6392\u5e8f http:\/\/zhidao.baidu.com\/question\/189798009.html \u8bb2\u7684\u662f\u8f93\u51fa\u586b0\u683c\u5f0f\u5316\u95ee\u9898 http:\/\/www.189works.com\/article-43335-1.html http:\/\/wenku.baidu.com\/view\/08c0eb0bff00bed5b9f31d29.html \u8fd9\u4e24\u4e2a\u5c31\u662f\u81ea\u5b9a\u4e49\u6392\u5e8f\u4e86
\n\u8fd9\u9898\u76ee\u8fd9\u4e48\u641e\u4e86\u4ee5\u540e\u5c31\u7b80\u5355\u591a\u4e86:)\u5f53\u7136\u6700\u540e\u4e00\u4e2a\u6d4b\u8bd5\u70b9\u8fd8\u662f\u7528\u4e86100ms…\u4e0d\u7ba1\u4e86\u8fc7\u4e86\u5c31\u884c ============================================<\/p>\n
#include\n#include\n#include\n#include\nusing namespace std;\nint compareName(const char name1[],const  char name2[])\n{\n    for(int i=0; i<8; i++)\n    {\n        if( name1[i] < name2[i] )\n            return 1;\n        else if(name1[i] > name2[i])\n            return -1;\n        \/\/\u76f8\u7b49\u7684\u8bdd\u7ee7\u7eed\u6bd4\u8f83\n    }\n    return 0; \/\/\u76f8\u540c\u7684\u540d\u5b57\n}\nstruct StudentRecord\n{\n    int ID;\n    char name[9];\n    int grade;\n    int sortType; \/\/\u6309\u54ea\u4e00\u5217\u6392\u5e8f\uff0c1,2,3\n    StudentRecord(){}\n    StudentRecord(int _id, char _name[], int _grade, int _sortType)\n    {\n        ID = _id;\n        strcpy(name, _name);\n        grade = _grade;\n        sortType = _sortType;\n    }\n    void set(int _id, char _name[], int _grade)\n    {\n        ID = _id;\n        strcpy(name, _name);\n        grade = _grade;\n    }\n    \/\/\u81ea\u5b9a\u4e49\u6392\u5e8f\u65b9\u6cd5\n    bool operator< (const StudentRecord& other) const\n    {\n        int cmpResult;\n        switch(sortType)\n        {\n        case 1:\n            \/\/\u6309\u7167ID\u5347\u5e8f\u6392\u5217\n            return ID < other.ID;\n        case 2:\n            \/\/\u6309\u7167\u59d3\u540d\u7684\u5347\u5e8f\u6392\u5217\uff0c\u5982\u679c\u6709\u540c\u540d\u518d\u6309ID\u5347\u5e8f\n            cmpResult = compareName(name, other.name);\n            if(cmpResult > 0)\n                return true;\n            else if (cmpResult < 0)\n                return false;\n            else\n                return ID < other.ID;\n        case 3:\n            \/\/\u6309\u7167\u6210\u7ee9\u7684\u5347\u5e8f\u6392\u5217\uff0c\u5982\u679c\u6709\u540c\u540d\u6210\u7ee9\u6309ID\u5347\u5e8f\n            if (grade == other.grade)\n                return ID < other.ID;\n            else\n                return grade < other.grade;\n        default:\n            printf(\"ERROR!\");\n            return false;\n        }\n    }\n};\nset records;\nint main()\n{\n    long N; int C;\n    scanf(\"%ld %d\", &N, &C);\n    StudentRecord singleRec;\n    singleRec.sortType = C;\n    for(long i=0; i<N; i++)\n    {\n        int ID, grade;\n        char name[8];\n        scanf(\"%d %s %d\", &ID, name, &grade);\n        singleRec.set(ID, name, grade);\n        records.insert(singleRec);\n    }\n    set::iterator it;\n    for(it = records.begin(); it != records.end(); it++)\n    {\n        StudentRecord sr = *it;\n        printf(\"%06d %s %dn\", sr.ID, sr.name, sr.grade);\n    }\n    return 0;\n}<\/pre>\n
====================================<\/p>\n
\u6d4b\u8bd5\u70b9<\/h2>\n\n\n\n\n\n\n\n\n\n\n\n
\u6d4b\u8bd5\u70b9<\/th>\n\u7ed3\u679c<\/th>\n\u7528\u65f6(ms)<\/th>\n\u5185\u5b58(kB)<\/th>\n\u5f97\u5206\/\u6ee1\u5206<\/th>\n<\/tr>\n<\/thead>\n
0<\/td>\n\u7b54\u6848\u6b63\u786e<\/td>\n0<\/td>\n790<\/td>\n5\/5<\/td>\n<\/tr>\n
1<\/td>\n\u7b54\u6848\u6b63\u786e<\/td>\n0<\/td>\n740<\/td>\n5\/5<\/td>\n<\/tr>\n
2<\/td>\n\u7b54\u6848\u6b63\u786e<\/td>\n0<\/td>\n750<\/td>\n5\/5<\/td>\n<\/tr>\n
3<\/td>\n\u7b54\u6848\u6b63\u786e<\/td>\n0<\/td>\n790<\/td>\n2\/2<\/td>\n<\/tr>\n
4<\/td>\n\u7b54\u6848\u6b63\u786e<\/td>\n0<\/td>\n790<\/td>\n2\/2<\/td>\n<\/tr>\n
5<\/td>\n\u7b54\u6848\u6b63\u786e<\/td>\n0<\/td>\n740<\/td>\n2\/2<\/td>\n<\/tr>\n
6<\/td>\n\u7b54\u6848\u6b63\u786e<\/td>\n100<\/td>\n8970<\/td>\n4\/4<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n","protected":false},"excerpt":{"rendered":"
\u65f6\u95f4\u9650\u5236 200 ms \u5185\u5b58\u9650\u5236 32000 kB \u4ee3\u7801\u957f\u5ea6\u9650\u5236 16000 B Excel can sort records according to any column. Now you are supposed to imitate this function. Input Each input file contains one test case. For each case, the first line contains two integers N (<=100000) and C, where N is the number of records and C […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[84],"class_list":["post-443","post","type-post","status-publish","format-standard","hentry","category-study","tag-pat"],"_links":{"self":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/443","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=443"}],"version-history":[{"count":0,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/443\/revisions"}],"wp:attachment":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=443"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=443"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=443"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}