PTA口罩发放问题,问题描述如下:
为了抗击来势汹汹的 COVID19 新型冠状病毒,全国各地均启动了各项措施控制疫情发展,其中一个重要的环节是口罩的发放。
某市出于给市民发放口罩的需要,推出了一款小程序让市民填写信息,方便工作的开展。小程序收集了各种信息,包括市民的姓名、身份证、身体情况、提交时间等,但因为数据量太大,需要根据一定规则进行筛选和处理,请你编写程序,按照给定规则输出口罩的寄送名单。
输入格式:
输入第一行是两个正整数 D 和 P(1≤D,P≤30),表示有 D 天的数据,市民两次获得口罩的时间至少需要间隔 P 天。
接下来 D 块数据,每块给出一天的申请信息。第 i 块数据(i=1,⋯,D)的第一行是两个整数 Ti 和 Si(1≤Ti,Si≤1000),表示在第 i 天有 Ti 条申请,总共有 Si 个口罩发放名额。随后 Ti 行,每行给出一条申请信息,格式如下:
姓名 身份证号 身体情况 提交时间
姓名 身份证号 身体情况 提交时间
给定数据约束如下:
姓名 是一个长度不超过 10 的不包含空格的非空字符串;
身份证号 是一个长度不超过 20 的非空字符串;
身体情况 是 0 或者 1,0 表示自觉良好,1 表示有相关症状;
提交时间 是 hh:mm,为24小时时间(由 00:00 到 23:59。例如 09:08。)。注意,给定的记录的提交时间不一定有序;
身份证号 各不相同,同一个身份证号被认为是同一个人,数据保证同一个身份证号姓名是相同的。
能发放口罩的记录要求如下:
身份证号 必须是 18 位的数字(可以包含前导0);
同一个身份证号若在第 i 天申请成功,则接下来的 P 天不能再次申请。也就是说,若第 i 天申请成功,则等到第 i+P+1 天才能再次申请;
在上面两条都符合的情况下,按照提交时间的先后顺序发放,直至全部记录处理完毕或 Si 个名额用完。如果提交时间相同,则按照在列表中出现的先后顺序决定。
输出格式:
对于每一天的申请记录,每行输出一位得到口罩的人的姓名及身份证号,用一个空格隔开。顺序按照发放顺序确定。
在输出完发放记录后,你还需要输出有合法记录的、身体状况为 1 的申请人的姓名及身份证号,用空格隔开。顺序按照申请记录中出现的顺序确定,同一个人只需要输出一次。
输入样例:
4 2
5 3
A 123456789012345670 1 13:58
B 123456789012345671 0 13:58
C 12345678901234567 0 13:22
D 123456789012345672 0 03:24
C 123456789012345673 0 13:59
4 3
A 123456789012345670 1 13:58
E 123456789012345674 0 13:59
C 123456789012345673 0 13:59
F F 0 14:00
1 3
E 123456789012345674 1 13:58
1 1
A 123456789012345670 0 14:11
输出样例:
D 123456789012345672
A 123456789012345670
B 123456789012345671
E 123456789012345674
C 123456789012345673
A 123456789012345670
A 123456789012345670
E 123456789012345674
样例解释:
输出中,第一行到第三行是第一天的部分;第四、五行是第二天的部分;第三天没有符合要求的市民;第六行是第四天的部分。最后两行按照出现顺序输出了可能存在身体不适的人员。
#include"stdio.h"
#include"stdlib.h"
#include"string.h"
#define in information
#define si saved_information
#define ssi saved_state_information
typedef struct Person{
char name[11]; //每个人的姓名,不超过十个字符串
char ID[21]; // 每个人的身份证号,不超过20个字符串
int state; //每个人的身体状态,0表示健康,1表示有状况
char time[6]; //每个人的提交时间,由五个字符串组成,hh:mm;
int order; //每个人的提交顺序
int date; //每个人申请成功的时间
}Per;
typedef struct saved_Person{
char name[11];
char ID[19]; //保存的个人信息的身份证号码
int date; //个人信息的申请成功的时间
}sp;
int check_ID(char *s); //检查身份证信息是否合格,合格输出为1,不合格输出为0
void swap(Per *a,Per *b);//比较两个人的提交时间以及提交顺序,使得先提交的在前,后提交的在后
void paixu(Per *p,int n);//对每天的信息按照时间顺序进行排序
void test(Per *p,int a); //调试输出
int main()
{
int D,P; //D天的数据,P表示间隔P天,对于同一ID在第i天领取,则在第i+1~i+P天不能领取,例如i=0,P=1,则在第2天才可以领取
scanf("%d %d",&D,&P);
int i,j,k,T[D],S[D]; // T[D]表示每天申请条数组成的数组,S[D]表示每天发放名额组成的数组
int cnt[D]; //cnt[D]用来表示每一天实际申请的信息当中的有效信息条数
int total_cnt=0,success_cnt=0,saved_cnt=0,saved_state_cnt=0;//总的申请条数,以及每天成功申请数以及保存的信息数
struct Person *information[D]; //表示有D块个人信息,每块个人信息的首地址在这个数组当中
for(i=0;i用来吸收换行的字符
in[i]=(Per*)malloc(sizeof(Per)*T[i]); //为每块信息申请空间,用来储存这T[i]条信息
cnt[i]=0;
for(j=0;jname,(in[i]+cnt[i])->ID,&(in[i]+cnt[i])->state,(in[i]+cnt[i])->time);
getchar(); // 用来吸收换行符
(in[i]+cnt[i])->order=cnt[i]; //给合格的信息赋予输入顺序
(in[i]+cnt[i])->date=-P-1; //初始化申请日期
if(check_ID((in[i]+cnt[i])->ID)) //如果身份证号符合要求,记录下来,否则舍弃
cnt[i]++;
}
total_cnt+=cnt[i];
}
sp *saved_information,*saved_state_information; //输出申请人的信息
si=(sp*)malloc(sizeof(sp)*total_cnt);
ssi=(sp*)malloc(sizeof(sp)*total_cnt);
for(i=0;i
{
for(j=0;j
{
if((in[i]+j)->state)
{
for(k=0;k
{
if(strcmp((ssi+k)->ID,(in[i]+j)->ID)==0)
break;
}
if(k==saved_state_cnt)
{
strcpy((ssi+saved_state_cnt)->name,(in[i]+j)->name);
strcpy((ssi+saved_state_cnt)->ID,(in[i]+j)->ID);
saved_state_cnt++;
}
}
}
}
for(i=0;i //给D天的信息进行排序
{
paixu(in[i],cnt[i]);
}
for(i=0;i
{
success_cnt=0;
for(j=0;j
{
if(success_cnt
{
for(k=0;k
{
if(strcmp((si+k)->ID,(in[i]+j)->ID)==0&&(si+k)->date+P>=i)
break;
}
if(k==saved_cnt)
{
printf("%s %s\n",(in[i]+j)->name,(in[i]+j)->ID);
strcpy((si+success_cnt)->ID,(in[i]+j)->ID);
(si+success_cnt)-> date=i;
success_cnt++;
saved_cnt++;
}
}
else
break;
}
}
for(i=0;i("%s %s\n",(ssi+i)->name,(ssi+i)->ID);
}
// for(i=0;i //测试输出
// {
// test(in[i],cnt[i]);
// }
// return 0;
}
int check_ID(char *s) //检查身份证信息是否合格,合格输出为1,不合格输出为0
{
int i;
if(strlen(s)!=18) //检查长度是否满足18位
return 0;
else
{
for(i=0;i<18;i++) //检查是否都是数字
{
if(*(s+i)<'0'||*(s+i)>'9')
return 0;
}
}
return 1;
}
void swap(Per *a,Per *b)//比较两个人的提交时间以及提交顺序,使得先提交的在前,后提交的在后
{
Per c;
if(strcmp(a->time,b->time)>0)
{
c=*a;
*a=*b;
*b=c;
}
else if(strcmp(a->time,b->time)==0)
{
if(a->order>b->order)
{
c=*a;
*a=*b;
*b=c;
}
}
}
void paixu(Per *p,int n)//对每天的信息按照时间顺序进行排序
{
int i,j;
for(i=0;i
{
for(j=i;j
{
swap((p+i),(p+j));
}
}
}
void test(Per *p,int a)//调试输出
{
printf("\n\n");
int i;
for(i=0;i
{
printf("%s %s %d %s %d\n",(p+i)->name,(p+i)->ID,(p+i)->state,(p+i)->time,(p+i)->order);
}
}
运行样例的结果和参考的结果一样,但是提交上去,还有其他测试点没过,不知道具体测试点是什么,感觉自己思路也没有问题,实在想不出来了具体哪里不对,求各位给点意见。
D表示有D天的数据,不是每天有D条数据,你数组长度为什么是D呀,第一天就有5条数据,这不都越界了吗
不确定有多少条数据你最好是用链表,这样排序的时候也不用整体挪来挪去的
数组很长的时候你这样排序肯定超时了呀