2020-07-01 个人训练赛后补题
我恨英文题，我真的那个恨啊！
放题：
题面翻译
一所学校里有编号分别为1~n的n个学生。这些学生每人有x本故事书和y个玩具。现在学校打算给孩子门开车送些玩具进来，但鉴于车辆有限，学校打算按规则专门给孩子们安排：
1、玩具更少的孩子优先；
2、如果孩子们玩具数量一致，那么拥有更多故事书的孩子优先；
3、如果孩子们手上故事书和玩具数量都相等，编号更高的孩子优先。
你的任务是找出孩子们接受礼物的顺序。
##input：
· 第一行包括N，表示有n个学生
· 接下来N行内每行包括两个整数X,Y，学生编号就是输入顺序所在的数字。
##output：
单独一行输出N个小孩排队顺序
##Constraints：
· 1<=N<=4*10^5
` 2<=X,Y<=100
//----------------------------------------------------------------
训练时WA代码：
runtime error：
1 #pragma warning (disable:4996) 2 #include <iostream> 3 #include<algorithm> 4 #include<stdio.h> 5 #include<math.h> 6 #include<string.h> 7 #include<string> 8 #define MAX1 400005 /*4e5 + 5*/ 9 #define MAX2 1000000005 /*le9 + 5*/ 10 #define MAX3 200005 /*1e5 + 5*/ 11 #define MAX4 5005 /*5e4 + 5*/ 12 #define T2 27 13 #define T3 18 14 using namespace std; 15 typedef long long int ll; 16 #define MOL 998244353 17 18 typedef struct { 19 int roll = 0; 20 int book = 0; 21 int toy = 0; 22 }child; 23 24 int isxby(child x, child y) {//x比y先拿到 25 if (x.toy > y.toy) return 0; 26 else if (x.toy == y.toy) { 27 if (x.book < y.book) return 0; 28 else if (x.book == y.book) { 29 if (x.roll < y.roll) return 0; 30 } 31 } 32 return 1; 33 } 34 void sb(child a[], int length, int dk) { 35 int i, j; 36 for (i = dk + 1; i <= length; ++i) { 37 if (isxby(a[i], a[i - dk])) { 38 a[0] = a[i]; 39 for (j = i - dk; j > 0 && isxby(a[0], a[j]); j -= dk) 40 a[j + dk] = a[j]; 41 a[j + dk] = a[0]; 42 } 43 } 44 } 45 void sort_xier(child a[], int length) { 46 int dt[3] = { 0 }; 47 dt[0] = 5; dt[1] = 3; dt[2] = 1; 48 for (int i = 0; i < 3; ++i) { 49 sb(a, length, dt[i]); 50 } 51 } 52 int main() { 53 int t, x, y; 54 child a[MAX4]; 55 while (scanf("%d", &t) != EOF) { 56 for (int k = 1; k <= t; ++k) { 57 scanf("%d %d", &x, &y); 58 a[k].book = x; 59 a[k].toy = y; 60 a[k].roll = k; 61 } 62 sort_xier(a, t); 63 for (int i = 1; i <= t; ++i) { 64 if (i != t)printf("%d ", a[i].roll); 65 else printf("%d\n", a[i].roll); 66 } 67 } 68 return 0; 69 }
上网查了一下（下面为复制黏贴）
SIGSEGV --- Segment Fault. The possible cases of your encountering this error are:
1.buffer overflow --- usually caused by a pointer reference out of range.
2.stack overflow --- please keep in mind that the default stack size is 8192K.
3.illegal file access --- file operations are forbidden on our judge system.
我看了一下自己的代码，可能失误是没申请结构体空间。
////------------------------------------------------
确实是没申请结构体空间，但改完又来个毛病：Timelimit
QAQ我以为希尔排序时间够短了
TimeLimit的主函数【其他部分没有变化】
1 int main() { 2 int t, x, y; 3 child* a = new child[MAX1]; 4 while (scanf("%d", &t) != EOF) { 5 for (int k = 1; k <= t; ++k) { 6 scanf("%d %d", &x, &y); 7 a[k].book = x; 8 a[k].toy = y; 9 a[k].roll = k; 10 } 11 sort_xier(a, t); 12 for (int i = 1; i <= t; ++i) { 13 if (i != t)printf("%d ", a[i].roll); 14 else printf("%d\n", a[i].roll); 15 } 16 } 17 delete a; 18 return 0; 19 }
////----------------------------------------------------
用系统自带的sort自己编一个cmp就能AC了
以下是AC代码：
1 #pragma warning (disable:4996) 2 #include <iostream> 3 #include<algorithm> 4 #include<stdio.h> 5 #include<math.h> 6 #include<string.h> 7 #include<string> 8 #define MAX1 400005 /*4e5 + 5*/ 9 #define MAX2 1000000005 /*le9 + 5*/ 10 #define MAX3 200005 /*1e5 + 5*/ 11 #define MAX4 5005 /*5e4 + 5*/ 12 #define T2 27 13 #define T3 18 14 using namespace std; 15 typedef long long int ll; 16 #define MOL 998244353 17 18 typedef struct { 19 int roll = 0; 20 int book = 0; 21 int toy = 0; 22 }child; 23 24 bool cmp(child x, child y) {//x比y先拿到 25 if (x.toy != y.toy) return x.toy < y.toy; 26 if (x.book != y.book)return x.book > y.book; 27 return x.roll > y.roll; 28 } 29 int main() { 30 int t, x, y; 31 child* a = new child[MAX1]; 32 while (scanf("%d", &t) != EOF) { 33 for (int k = 1; k <= t; ++k) { 34 scanf("%d %d", &x, &y); 35 a[k].book = x; 36 a[k].toy = y; 37 a[k].roll = k; 38 } 39 sort(a + 1, a + t + 1, cmp); 40 for (int i = 1; i <= t; ++i) { 41 if (i != t)printf("%d ", a[i].roll); 42 else printf("%d\n", a[i].roll); 43 } 44 } 45 delete a; 46 return 0; 47 }
原文：https://www.cnblogs.com/nfyyzz/p/13274015.html