百度网站链接,手机新机价格网站,实体店做团购有那些网站,paypal网站集成由于这道题在留的作业中#xff0c;排序和查找都有#xff0c;所以我先写这道题#xff08;图的先放放#xff09; “单身狗”是中文对于单身人士的一种爱称。本题请你从上万人的大型派对中找出落单的客人#xff0c;以便给予特殊关爱。
输入格式#xff1a;
输入第一行… 由于这道题在留的作业中排序和查找都有所以我先写这道题图的先放放 “单身狗”是中文对于单身人士的一种爱称。本题请你从上万人的大型派对中找出落单的客人以便给予特殊关爱。
输入格式
输入第一行给出一个正整数 N≤50000是已知夫妻/伴侣的对数随后 N 行每行给出一对夫妻/伴侣——为方便起见每人对应一个 ID 号为 5 位数字从 00000 到 99999ID 间以空格分隔之后给出一个正整数 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大的话是1int yeah; //有对象1为有0为无2为查找的时候已经找到过他对象了
}Couple; 下标当作id来存一个人的信息。
如何查找顺便找到单身人数 先排序一下输入的人的id小的在前面。然后开始遍历来的人也就是数组man。如果一个人在couple中的yeah值为1而且BOrSbig or small为1那么就去往后找他的对象来没来没来就进入单身行列来了就不是。如果BOrS为-1因为是从前往后从小往大id找对象的他要是被找过那只能说他对象比他小且yeah已经被置为了2那么检查他的yeahyeah不是2就进入单身行列。其余yeah都是0那只能也进入单身行列。
int Search(Couple c[],int man[], int nums,int single[]){int flag 0;for (int i 0;inums;i) {if (c[man[i]].yeah 1) {if (c[man[i]].BOrS 1) {int judge 0;for (int j i 1; j nums; j) {if (c[man[j]].his_couple man[i]) { //有他伴侣c[man[j]].yeah 2; //已经检查过了judge 1;break;}}if(judge 0)single[flag] man[i];}if ((c[man[i]].BOrS -1)(c[man[i]].yeah ! 2)) {single[flag] man[i];}}else if(c[man[i]].yeah 2) {continue;}else {single[flag] man[i];}}return flag;
}
输出打印 因为man已经排好序了所以得到的single数组也应当是有序的所以直接打印就行然后注意一下空格和0补位。之前写过补位代码直接拿过来。space处理空格问题具体见主函数传参。 void Print(int id,int space){if(id -1)return;if(id10000)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 stdio.h
#include malloc.h
#define MAX 100000typedef 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] temp i j) {i;}if(i j) {int t array[j];array[j] array[i];array[i] t;}}int t array[low];array[low] array[i];array[i] t;QuickSort(array, low, i - 1);QuickSort(array, i 1, high);
}int Search(Couple c[],int man[], int nums,int single[]){int flag 0;for (int i 0;inums;i) {if (c[man[i]].yeah 1) {if (c[man[i]].BOrS 1) {int judge 0;for (int j i 1; j nums; j) {if (c[man[j]].his_couple man[i]) { //有他伴侣c[man[j]].yeah 2; //已经检查过了judge 1;break;}}if(judge 0)single[flag] man[i];}if ((c[man[i]].BOrS -1)(c[man[i]].yeah ! 2)) {single[flag] man[i];}}else if(c[man[i]].yeah 2) {continue;}else {single[flag] man[i];}}return flag;
}void Print(int id,int space){if(id -1)return;if(id10000)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( );
}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(xy){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
很有意义的一道题
