题目链接
输入样例:
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
样例解释:
- 输出中,第一行到第三行是第一天的部分;第四、五行是第二天的部分;第三天没有符合要求的市民;第六行是第四天的部分。最后两行按照出现顺序输出了可能存在身体不适的人员。
测试点:
备注:
- 测试点6 卡是否按照排队顺序排序
- 测试点7 卡是否一天被发多次口罩
- 测试点8 卡同一身份证多个名字
答案:
法一:
判断能否发放口罩后再存入,需要在发放口罩的过程中判断当天是否发过
#include <iostream>
#include<bits/stdc++.h>
#define ll long long
#define PII pair<int,int>
#define PSS pair<string,string>
#define PSI pair<string,int>
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a))
#define x first
#define y second
const int N = 3e5 + 10;
using namespace std;
struct node{ ///定义结构体
string s; ///姓名
string id; ///身份证号
int body; ///身体状况
int hh; ///小时
int mm; ///分钟
int pos; ///排队序号
}dp[N];
map<string,int>day; ///发放口罩时间
set<PSS>st; ///记录患病信息是否重复
vector<PSS>peo; /// 记录患病人群信息
vector<PSS>ans; /// 记录发口罩记录
vector<node>vp; /// 记录每一回合可以发口罩
set<string>sp; /// 记录当天发口罩人群信息
bool cmp(node x,node y){ ///排序
if(x.hh!=y.hh) return x.hh<y.hh;
else if(x.mm!=y.mm) return x.mm<y.mm;
else return x.pos<y.pos;
}
int main(){
int d,p;
cin>>d>>p;
for(int dd=1;dd<=d;dd++){
int t,s;
cin>>t>>s;
char c;
vp.clear();
for(int i=1;i<=t;i++){
cin>>dp[i].s>>dp[i].id>>dp[i].body>>dp[i].hh>>c>>dp[i].mm;
dp[i].pos=i;
int len=dp[i].id.size();
if(len!=18) continue; ///判断身份证长度是否符合条件
bool flag=0;
for(int j=0;j<len;j++){ ///判断身份证是否每一位都是数字
if(!isdigit(dp[i].id[j])){
flag=1;
break;
}
}
if(flag) continue;
if(dp[i].body) peo.pb(PSS{dp[i].s,dp[i].id}); ///记录患病人群信息
if(day[dp[i].id]+p<dd||!day[dp[i].id]) vp.pb(dp[i]); ///可以发口罩的信息存到vp中
}
sort(vp.begin(),vp.end(),cmp); ///排序
int len=vp.size();
sp.clear(); ///sp数组清空
for(int i=0;i<len;i++){
if(!s) break; ///判断口罩是否发完
if(!sp.count(vp[i].id)){ ///判断是否今天发过口罩
ans.pb(PSS{vp[i].s,vp[i].id}); ///存入ans最后输出
sp.insert(vp[i].id); ///记录今天发过口罩
day[vp[i].id]=dd; ///更新时间
s--; ///剩余口罩数量-1
}
}
}
for(int i=0;i<(int)ans.size();i++){ ///输出发放口罩信息
cout<<ans[i].x<<" "<<ans[i].y<<endl;
}
for(int i=0;i<(int)peo.size();i++){ ///输出患病人群信息
if(!st.count(peo[i])){ ///判断是否输出
cout<<peo[i].x<<" "<<peo[i].y<<endl;
st.insert(peo[i]);
}
}
return 0;
}
法二:
身份证符合条件的都存入,判断能否发放口罩后修改时间,不需要在发放口罩的过程中判断当天是否发过(部分注释详见法一)
#include <iostream>
#include <bits/stdc++.h>
#define ll long long
#define PII pair<int, int>
#define PSS pair<string, string>
#define PSI pair<string, int>
#define pb push_back
#define mem(a, b) memset(a, b, sizeof(a))
#define x first
#define y second
const int N = 3e5 + 10;
using namespace std;
struct node
{
string s;
string id;
int body;
int hh;
int mm;
int pos;
} dp[N];
map<string, int> day;
set<PSS> st;
vector<PSS> peo;
vector<PSS> ans;
vector<node> vp;
bool cmp(node x, node y)
{
if (x.hh != y.hh)
return x.hh < y.hh;
else if (x.mm != y.mm)
return x.mm < y.mm;
else
return x.pos < y.pos;
}
int main()
{
int d, p;
cin >> d >> p;
day.clear();
for (int dd = 1; dd <= d; dd++)
{
int t, s;
cin >> t >> s;
char c;
vp.clear();
for (int i = 1; i <= t; i++)
{
cin >> dp[i].s >> dp[i].id >> dp[i].body >> dp[i].hh >> c >> dp[i].mm;
dp[i].pos = i;
int len = dp[i].id.size();
if (len != 18)
continue;
bool flag = 0;
for (int j = 0; j < 18; j++)
{
if (!isdigit(dp[i].id[j]))
{
flag = 1;
break;
}
}
if (flag)
continue;
if (dp[i].body)
peo.pb(PSS{dp[i].s, dp[i].id});
vp.pb(dp[i]);
}
sort(vp.begin(), vp.end(), cmp);
int len = vp.size();
for (int i = 0; i < len; i++)
{
if (!s)
break;
if (day[dp[i].id] + p < dd || !day[dp[i].id]){
ans.pb(PSS{vp[i].s, vp[i].id});
day[vp[i].id] = dd;
s--;
}
else continue;
}
}
for (int i = 0; i < (int)ans.size(); i++)
{
cout << ans[i].x << " " << ans[i].y << endl;
}
for (int i = 0; i < (int)peo.size(); i++)
{
if (!st.count(peo[i]))
{
cout << peo[i].x << " " << peo[i].y << endl;
st.insert(peo[i]);
}
}
return 0;
}