| 7 | 您所在的位置：网站首页 › 单身狗的悲哀图片 › 7 |
7
|
由于这道题在留的作业中，排序和查找都有，所以我先写这道题（图的先放放） “单身狗”是中文对于单身人士的一种爱称。本题请你从上万人的大型派对中找出落单的客人，以便给予特殊关爱。 输入格式：输入第一行给出一个正整数 N（≤50000），是已知夫妻/伴侣的对数；随后 N 行，每行给出一对夫妻/伴侣——为方便起见，每人对应一个 ID 号，为 5 位数字（从 00000 到 99999），ID 间以空格分隔；之后给出一个正整数 M（≤10000），为参加派对的总人数；随后一行给出这 M 位客人的 ID，以空格分隔。题目保证无人重婚或脚踩两条船。 输出格式：首先第一行输出落单客人的总人数；随后第二行按 ID 递增顺序列出落单的客人。ID 间用 1 个空格分隔，行的首尾不得有多余空格。 输入样例： 3 11111 22222 33333 44444 55555 66666 7 55555 44444 10000 88888 22222 11111 23333 输出样例： 5 10000 23333 44444 55555 88888代码长度限制 16 KB 时间限制 200 ms 内存限制 64 MB 提交结果：
要找，要排，限制了时间。 排序的话，这里使用了快速排序算法（真的很快！），其他有人用的堆排序，可以去尝试一下。找就得自己想办法找了。 如何输入：题目中给的是一对一对的，所以这里考虑要整个结构体去存： typedef struct { int his_couple; //他的对象 int BOrS; //对象比他大还是小，小的话是-1，大的话是1 int yeah; //有对象，1为有，0为无，2为查找的时候已经找到过他对象了 }Couple;下标当作id来存一个人的信息。 如何查找（顺便找到单身人数）：先排序一下输入的人的id，小的在前面。然后开始遍历来的人，也就是数组man。如果一个人在couple中的yeah值为1，而且BOrS（big or small）为1，那么就去往后找他的对象来没来，没来就进入单身行列，来了就不是。如果BOrS为-1（因为是从前往后，从小往大id找对象的，他要是被找过，那只能说他对象比他小，且yeah已经被置为了2），那么检查他的yeah，yeah不是2就进入单身行列。其余yeah都是0，那只能也进入单身行列。 int Search(Couple c[],int man[], int nums,int single[]){ int flag = 0; for (int i = 0;i=10000) printf("%d",id); else if(id >= 1000) printf("0%d",id); else if(id >= 100) printf("00%d",id); else if(id >= 10){ printf("000%d",id); } else if(id >= 0){ printf("0000%d",id); } if(space == 1) printf(" "); } 注意：一定要初始化结构体数组！！！ 代码展示： // // Created by DDD on 2023/12/19. // #include #include #define MAX 100000 typedef struct { int his_couple; int BOrS; int yeah; }Couple; void QuickSort(int array[], int low, int high) { //快排 int i = low; int j = high; if(i >= j) { return; } int temp = array[low]; while(i != j) { while(array[j] >= temp && i < j) { j--; } while(array[i] = 1000) printf("0%d",id); else if(id >= 100) printf("00%d",id); else if(id >= 10){ printf("000%d",id); } else if(id >= 0){ printf("0000%d",id); } if(space == 1) printf(" "); } int main(){ int n; scanf("%d",&n); Couple c[MAX]={0}; for (int i = 0; i < n; ++i) { int x, y; scanf("%d %d",&x,&y); c[x].his_couple = y; c[y].his_couple = x; c[x].yeah = 1; c[y].yeah = 1; //有伴侣 if(x>y){ c[x].BOrS = -1; //他的伴侣比他小 c[y].BOrS = 1; } else{ c[x].BOrS = 1; c[y].BOrS = -1; } } int m; scanf("%d",&m); int man[m]; for (int i = 0; i < m; ++i) { scanf("%d",&man[i]); } int single[m]; QuickSort(man,0,m-1); if(n!=0) { int flag = Search(c, man, m, single); printf("%d\n", flag); for (int i = 0; i < flag; ++i) { if (i < flag - 1) Print(single[i],1); else { Print(single[i],0); } } } else{ printf("%d\n",m); for (int i = 0; i < m; ++i) { if (i < m - 1) Print(man[i],1); else { Print(man[i],0); } } } }return 0;//祝大家早日离开single，把自己的yeah置为1！！ （很有意义的一道题） |
【本文地址】
| 今日新闻 |
| 推荐新闻 |
| 专题文章 |