AI 助理
备案控制台
开发者社区 云计算 文章 正文

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

2022-05-21 172
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 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 */
Lux_Sun
目录
相关文章
ZLOSER02
|
C++
C/C++判断字符串是否为另一字符串的子字符串
C/C++判断字符串是否为另一字符串的子字符串
ZLOSER02
295 0
一个处女座的程序猿
|
机器学习/深度学习 Python
Py之lime：lime库的简介、安装、使用方法之详细攻略
Py之lime：lime库的简介、安装、使用方法之详细攻略
一个处女座的程序猿
995 0
Py之lime：lime库的简介、安装、使用方法之详细攻略
算法码上来
|
机器学习/深度学习 人工智能 自然语言处理
养成女友？我训练出了一个“杨超越”聊天机器人
养成女友？我训练出了一个“杨超越”聊天机器人
算法码上来
310 0
王磊-phper
|
Web App开发 算法 安全
详细讲解https证书openssl公钥私钥以及ssh公钥私钥的生成以及使用
详细讲解https证书openssl公钥私钥以及ssh公钥私钥的生成以及使用
王磊-phper
2185 0
详细讲解https证书openssl公钥私钥以及ssh公钥私钥的生成以及使用
架构精进之路
|
NoSQL 前端开发 Redis
干货 | Redis 实现发布订阅原理与实践
Redis 是完全开源的，高性能的 key-value 数据库，受到越来越多的业务场景应用。对于"发布/订阅"的消息模式，大家也许都比较了解，但是其实现原理及应用是否还存在模糊呢？
架构精进之路
1290 0
干货 | Redis 实现发布订阅原理与实践
CastenWang
|
索引
PAT甲级 1007. Maximum Subsequence Sum(25分) 复杂度优化到O(n)
PAT甲级 1007. Maximum Subsequence Sum(25分) 复杂度优化到O(n)
CastenWang
113 0
游客a6klr54fksfbs
|
弹性计算 Linux
体验总结
上手难度低 官网查询便捷
游客a6klr54fksfbs
297 0
体验总结
阿里云头条
|
前端开发 JavaScript 定位技术
阿里自主研发的互动游戏引擎Hilo开源啦！【内有详解】
Hilo，一套HTML5跨终端的互动游戏解决方案开源啦！。Hilo支持了多届淘宝&天猫狂欢城等双十一大型和日常营销活动。内核极简，提供包括DOM，Canvas，Flash，WebGL等多种渲染方案，满足全终端和性能要求。详细介绍见内文。
阿里云头条
42486 0
uiiuiiu
|
文件存储
1019. General Palindromic Number (20)
A number that will be the same when it is written forwards or backwards is known as a Palindromic Number.
uiiuiiu
939 0
橘子红了呐
|
SQL 存储
decimal(numeric )、float 和 real 数据类型的区别[转]
橘子红了呐
1196 0