首页 > 代码库 > [洛谷201704R1]开心派对小火车
[洛谷201704R1]开心派对小火车
OJ题号：洛谷P3697
思路：
贪心。首先从起点出发，开特急电车，对于每一个特急车站$s_{i}$，分别下一次车，计算从当前车站$s_{i}$出发坐各停电车在指定时限内$t$最远能够到达的车站$r_{i}$，并保证这个$r_{i}$不会超过$s_{i+1}$。将得到的站点$r_{i}$放入一个大根堆中，堆中的每个元素记录两个值，第一个用来保存如果在当前站点开通快速电车，从当前站点坐快速电车总共能到达的站的个数；第二个用来保存当前站的编号$r_i$。最后不断地从堆中挑选最优的站，重复拓展到新的站点，并将新的站点放入堆中。用$ans$保存能够经过的站的个数，注意最后一个拓展的站$r$并不能到达，因此$ans$初值为$-1$。
优化：
用pb_ds的优先队列$(3ms)$比stl的优先队列$(0ms)$快。
1 #include<cstdio> 2 #include<queue> 3 #include<algorithm> 4 #include<ext/pb_ds/priority_queue.hpp> 5 const int maxm=3002; 6 typedef long long ll; 7 ll n,m,k,a,b,c,t,s[maxm],r[maxm],ans=-1,i; 8 __gnu_pbds::priority_queue<std::pair<int,int> > pq; 9 inline void push(const int i) {10 ll v=t-s[i]*b-(r[i]-s[i])*c;11 if(v<0) {12 pq.push(std::make_pair(0,i));13 return;14 }15 ll ri=r[i];16 r[i]=std::min(r[i]+v/a+1,s[i+1]);17 pq.push(std::make_pair(r[i]-ri,i));18 }19 int main() {20 scanf("%lld%lld%lld%lld%lld%lld%lld",&n,&m,&k,&a,&b,&c,&t);21 for(i=1;i<=m;i++) {22 scanf("%lld",&s[i]);23 s[i]--;24 }25 s[m+1]=n;26 for(i=1;(i<=m)&&(s[i]*b<=t);i++) {27 r[i]=std::min(s[i]+(t-s[i]*b)/a+1,s[i+1]);28 ans+=r[i]-s[i];29 push(i);30 }31 for(i=k-m;i--;) {32 ans+=pq.top().first;33 push(pq.top().second);34 pq.pop();35 }36 printf("%lld",ans);37 return 0;38 }
[洛谷201704R1]开心派对小火车
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。