2019 CSP-J 题目整理
B-公交换乘
思路梳理
先想暴力算法,一遇到公交车,就在已出现过的优惠卷中寻找价格大于等于公交车票价,并且出现时间最早且没有用过的优惠卷,时间复杂度为 \(O(n^2)\),必然会炸。但是注意题目中给到的特殊性质,要求如果优惠卷有效,则
\[t_{bus}-t_{subway}\le45 \]并且“不会有两次乘车记录出现在同一分钟”所以,只需要,查找前面有效的优惠卷,因为车票是按时间顺寻给出的,所以只要一遇到无效车票就 \(break\),就可以将时间复杂度优化到 \(O(kn),k\le45\)
代码实现
#include<bits/stdc++.h>
#define maxn 500010
using namespace std;
struct node{
int w,t;
}q[maxn];
int n,opt,tot=0,ans=0;
bool vis[maxn];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
int t,w;
cin>>opt>>w>>t;
if(opt==0){
q[++tot].t=t;
q[tot].w=w;
ans+=w;
}
else{
int cur=-1;
for(int j=tot;j>=1;j--){
if(t-q[j].t>45)break;
if(q[j].w>=w&&!vis[j]){
cur=j;
}
}
if(cur!=-1)vis[cur]=1;
else ans+=w;
}
}
cout<<ans;
return 0;
}
标签:cur,int,优惠卷,tot,2019,maxn,CSP,刷题
From: https://www.cnblogs.com/GSNforces/p/18434341