PAT (Advanced Level) Practice - 1026 Table Tennis（30 分）-阿里云开发者社区

PAT (Advanced Level) Practice - 1026 Table Tennis（30 分）

2022-05-21 134

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： PAT (Advanced Level) Practice - 1026 Table Tennis（30 分）

题目链接：点击打开链接

题目大意：略。

解题思路：

如果VIP客户遇到序号小的普通桌子和序号大的VIP桌子，优先选择VIP桌；如果VIP桌没有了，VIP客户和普通客户是平等的，VIP客户就不能插队了。

客户、桌子：总的一队，VIP的一队。

注意1：这里因为中途发现桌子用优先队列来做不方便，所以改用set来做：

VIP桌被占用后记得总桌子需要删除对应的VIP桌子；反之，总桌子在使用过程中，遇到使用VIP桌子时，在VIP桌子队中也要删除对应的VIP桌子。

注意2：(p.stime-p.atime)/60.0+1e-4，丢失精度问题。

AC 代码

#include<bits/stdc++.h>#include<cmath>#define mem(a,b) memset(a,b,sizeof a)#define ssclr(ss) ss.clear(), ss.str("")#define INF 0x3f3f3f3f#define MOD 1000000007usingnamespacestd;
typedeflonglongll;
constintmaxn=1e4+10;
structpeo{
intah,am,as,sh,sm,ss;
intatime,stime,ptime;
intvip;
}ps[maxn];
structplayer{
inttid,pid,etime;
player(){}
player(inttid,intpid,intetime):tid(tid),pid(pid),etime(etime){}
friendbooloperator<(playerp1,playerp2)
    {
returnp1.etime>p2.etime;
    }
};
priority_queue<player>pq;
set<int>tbpq, vtbpq;
vector<int>tbv, vipv;
intvis[maxn], cnt[200];
intcmp1(peop1,peop2)
{
returnp1.atime<p2.atime;
}
intcmp2(peop1,peop2)
{
returnp1.stime<p2.stime;
}
intmain()
{
intn,h,m,s,ptime,vip,k,kvip;
scanf("%d",&n);
for(inti=0;i<n;i++)
    {
scanf("%d:%d:%d%d%d",&h,&m,&s,&ptime,&vip);
if(ptime>120) ptime=120;
ps[i].ah=h, ps[i].am=m, ps[i].as=s, ps[i].ptime=ptime*60, ps[i].vip=vip;
ps[i].atime=ps[i].ah*3600+ps[i].am*60+ps[i].as;
    }
sort(ps,ps+n,cmp1);
for(inti=0;i<n;i++) if(ps[i].vip==1) vipv.push_back(i);
scanf("%d%d",&k,&kvip);
tbv.resize(k+1);
for(inti=1;i<=kvip;i++) scanf("%d",&vip), tbv[vip]=1;
for(inti=1;i<=k;i++)
    {
tbpq.insert(i);
if(tbv[i]==1) vtbpq.insert(i);
    }
intl1=0, l2=0;
for(intt=28800; t<75600&&l1<n;)
    {
while(l1<n&&vis[l1]==1) l1++;
if(l1==n) break;
if(ps[l1].atime>t)
        {
t=ps[l1].atime;
continue;
        }
elseif(!pq.empty() &&pq.top().etime>t&&tbpq.empty())
        {
t=pq.top().etime;
continue;
        }
while(!pq.empty()) // 清理 ps[l1].atime<=t        {
intf=0;
playerpla=pq.top();
if(pla.etime<=t)
            {
tbpq.insert(pla.tid);
if(tbv[pla.tid]==1) vtbpq.insert(pla.tid);
pq.pop();
f=1;
            }
if(!f) break;
        }
if(tbpq.empty()) continue;
while(1) // 有空位 + 有人        {
while(l1<n&&vis[l1]==1) l1++;
while(l2<vipv.size() &&vis[vipv[l2]]==1) l2++;
if(l1==n||tbpq.empty() ||ps[l1].atime>t) break;
inttid;
if(!vtbpq.empty() &&l2<vipv.size() &&ps[vipv[l2]].atime<=t) // VIP席遇上对的人            {
autoit=vtbpq.begin();
tid=*it, vtbpq.erase(it), tbpq.erase(tbpq.find(*it));
ps[vipv[l2]].stime=t;
pq.push(player(tid,vipv[l2],ps[vipv[l2]].ptime+t));
vis[vipv[l2]]=1;
            }
else            {
autoit=tbpq.begin();
tid=*it, tbpq.erase(it);
if(tbv[tid]==1)
vtbpq.erase(vtbpq.find(tid));
ps[l1].stime=t;
pq.push(player(tid,l1,ps[l1].ptime+t));
vis[l1]=1;
            }
cnt[tid]++;
        }
    }
sort(ps,ps+n,cmp2);
for(inti=0;i<n;i++)
    {
peo&p=ps[i];
if(p.stime==0) continue;
printf("%02d:%02d:%02d %02d:%02d:%02d %.0f\n",p.ah,p.am,p.as,p.stime/3600,p.stime%3600/60,p.stime%60,(p.stime-p.atime)/60.0+1e-4);
    }
for(inti=1;i<=k;i++) printf("%d%c",cnt[i],i==k?'\n':' ');
return0;
}

Debug 代码

#include<bits/stdc++.h>#include<cmath>#define mem(a,b) memset(a,b,sizeof a)#define ssclr(ss) ss.clear(), ss.str("")#define INF 0x3f3f3f3f#define MOD 1000000007usingnamespacestd;
typedeflonglongll;
constintmaxn=1e4+10;
structpeo{
intah,am,as,sh,sm,ss;
intatime,stime,ptime;
intvip;
}ps[maxn];
structplayer{
inttid,pid,etime;
player(){}
player(inttid,intpid,intetime):tid(tid),pid(pid),etime(etime){}
friendbooloperator<(playerp1,playerp2)
    {
returnp1.etime>p2.etime;
    }
};
priority_queue<player>pq;
set<int>tbpq, vtbpq;
vector<int>tbv, vipv;
intvis[maxn], cnt[200];
intcmp1(peop1,peop2)
{
returnp1.atime<p2.atime;
}
intcmp2(peop1,peop2)
{
returnp1.stime<p2.stime;
}
voidshow(intlen)
{
puts("-------------");
for(inti=0;i<len;i++)
    {
peo&p=ps[i];
printf("%02d:%02d:%02d %d %d %d\n",p.ah,p.am,p.as,p.ptime/60,p.vip,p.atime);
    }
puts("-------------");
}
voidshowPQ()
{
puts("-------------");
if(!pq.empty())
    {
intet=pq.top().etime;
printf("%02d:%02d:%02d\n",et/3600,et%3600/60,et%60);
    }
puts("-------------");
}
intmain()
{
intn,h,m,s,ptime,vip,k,kvip;
scanf("%d",&n);
for(inti=0;i<n;i++)
    {
scanf("%d:%d:%d%d%d",&h,&m,&s,&ptime,&vip);
if(ptime>120) ptime=120;
ps[i].ah=h, ps[i].am=m, ps[i].as=s, ps[i].ptime=ptime*60, ps[i].vip=vip;
ps[i].atime=ps[i].ah*3600+ps[i].am*60+ps[i].as;
    }
sort(ps,ps+n,cmp1);
for(inti=0;i<n;i++) if(ps[i].vip==1) vipv.push_back(i);
scanf("%d%d",&k,&kvip);
tbv.resize(k+1);
for(inti=1;i<=kvip;i++)
    {
scanf("%d",&vip);
tbv[vip]=1;
    }
for(inti=1;i<=k;i++)
    {
tbpq.insert(i);
if(tbv[i]==1) vtbpq.insert(i);
    }
//    show(n);intl1=0, l2=0;
for(intt=28800; t<75600&&l1<n;)
    {
//        printf("-------\n%02d:%02d:%02d\n-------\n",t/3600,t%3600/60,t%60);// 原理上一个一个接下来是不会有失效的，这么做是避免碰到VIP已经使用了的客户while(l1<n&&vis[l1]==1)
l1++;
if(l1==n) break;
if(ps[l1].atime>t)
        {
t=ps[l1].atime;
continue;
        }
elseif(!pq.empty() &&pq.top().etime>t&&tbpq.empty())
        {
t=pq.top().etime;
continue;
        }
// ps[l1].atime<=twhile(!pq.empty()) // 清理        {
intf=0;
playerpla=pq.top();
if(pla.etime<=t)
            {
tbpq.insert(pla.tid);
if(tbv[pla.tid]==1) vtbpq.insert(pla.tid);
pq.pop();
f=1;
            }
if(!f) break;
        }
if(tbpq.empty()) continue;
while(1) // 有空位 + 有人        {
while(l1<n&&vis[l1]==1)
l1++;
while(l2<vipv.size() &&vis[vipv[l2]]==1)
l2++;
if(l1==n) break;
if(tbpq.empty() ||ps[l1].atime>t) break;
inttid;
if(!vtbpq.empty() &&l2<vipv.size() &&ps[vipv[l2]].atime<=t) // VIP席遇上对的人            {
autoit=vtbpq.begin();
tid=*it, vtbpq.erase(it), tbpq.erase(tbpq.find(*it));
ps[vipv[l2]].stime=t;
pq.push(player(tid,vipv[l2],ps[vipv[l2]].ptime+t));
vis[vipv[l2]]=1;
            }
else            {
autoit=tbpq.begin();
tid=*it, tbpq.erase(it);
if(tbv[tid]==1)
vtbpq.erase(vtbpq.find(tid));
ps[l1].stime=t;
pq.push(player(tid,l1,ps[l1].ptime+t));
vis[l1]=1;
            }
cnt[tid]++;
//            showPQ();        }
    }
sort(ps,ps+n,cmp2);
for(inti=0;i<n;i++)
    {
peo&p=ps[i];
if(p.stime==0) continue;
printf("%02d:%02d:%02d %02d:%02d:%02d %.0f\n",p.ah,p.am,p.as,p.stime/3600,p.stime%3600/60,p.stime%60,(p.stime-p.atime)/60.0+1e-4);
    }
for(inti=1;i<=k;i++) printf("%d%c",cnt[i],i==k?'\n':' ');
return0;
}
/* 特殊样例319:29:59 75 108:08:42 33 108:24:14 120 13 12 */

PAT (Advanced Level) Practice - 1026 Table Tennis（30 分）

热门文章

最新文章

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

PAT (Advanced Level) Practice - 1026 Table Tennis（30 分）

热门文章

最新文章

相关电子书