P5661 公交换乘

CCF2020 CSP-j2第二题

https://www.luogu.com.cn/problem/P5661

方法一：纯模拟（40分）

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n, bs[100005], p[100005], t[100005]; 
 4 long long ans;
 5 int main()
 6 {
 7     cin>>n;
 8     for(int i=1; i<=n; i++){
 9         cin>>bs[i]>>p[i]>>t[i];
10         if(bs[i]==0)//如果是地铁，答案累加 
11             ans+=p[i];
12         if(bs[i]==1){//公交车的情况 
13             bool f=1;//判断是否使用优惠卷 ，假定没有 
14             for(int j=1; j<i; j++){//枚举[1,i-1]看是否存在符合条件的优惠卷 
15                 if(t[j]+45>=t[i] && p[j]>=p[i] && bs[j]==0){//符合条件：1.tbus-tsubway≤45  2.p[j]>=p[i]  3.bs[i]用于判断是否被使用过，避免重复使用 
16                     bs[j]=1;//标记被使用过，防止再次使用 
17                     f=0;//使用过优惠卷 
18                     break;
19                 }
20             }
21             if(f)ans+=p[i];//如果没有使用优惠卷则，票价被累加到答案 
22         }
23     }
24     cout<<ans;
25     return 0;
26 }

方法二：模拟（赵扬墨琮优化版）100分

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 struct node
 4 {
 5     int c,p,t;
 6 };
 7 node jl[100005];
 8 int n;
 9 int m;
10 int main()
11 {
12     freopen("transfer.in","r",stdin);
13     freopen("transfer.out","w",stdout);
14     cin>>n;
15     for(int i=0;i<n;i++) 
16     {
17         cin>>jl[i].c>>jl[i].p>>jl[i].t;
18     }
19     for(int i=0;i<n;i++)
20     {
21         if(!jl[i].c)
22         {
23             m+=jl[i].p;
24         }
25         else
26         {
27             int f=0;
28             for(int j=((i<45)?(0):(i-45));j<i;j++)
29             {
30                 if((!jl[j].c)&&jl[i].t-jl[j].t<=45&&jl[i].p<=jl[j].p)
31                 {
32                     f=1;
33                     jl[j].p=0;
34                     break;
35                 }
36             }
37             if(!f)
38             {
39                 m+=jl[i].p;
40             }
41         }
42     }
43     cout<<m<<endl;
44     return 0;
45 }

方法三：模拟+二分优化

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n, bs[100005], p[100005], t[100005]; 
 4 long long ans;
 5 int erfen(int x, int i){
 6     int l=1, r=i-1;//在t数组的[l,r]之间找答案 
 7     int ans=-1;
 8     while(l<=r){
 9         int mid=(l+r)/2;
10         if(t[mid]>=x){
11             r=mid-1;
12             ans=mid;
13         }
14         else
15             l=mid+1;
16     }
17     return ans;
18 }
19 int main()
20 {
21     cin>>n;
22     for(int i=1; i<=n; i++){
23         cin>>bs[i]>>p[i]>>t[i];
24         if(bs[i]==0)
25             ans+=p[i];
26         if(bs[i]==1){
27             bool f=1;
28             int js=erfen(t[i]-45, i);//利用二分答案，在[1, i-1]区间，查找 >=t[i]-45的最小值 
29             if(js!=-1)//找到符合条件的情况 
30             {
31                 for(int j=js; j<i; j++){
32                     if(p[j]>=p[i] && bs[j]==0){
33                         bs[j]=1;
34                         f=0;
35                         break;
36                     }
37                 }
38             }
39             if(f)
40                 ans+=p[i];
41         }
42     }
43     cout<<ans;
44     return 0;
45 }

方法四：用队列模拟增票盒子

https://www.luogu.com.cn/blog/nitubenben/p5661-gong-jiao-huan-sheng-ti-xie#