题解 P5661 【公交换乘【民间数据】】

CNF_Acceptance · 2019-11-23 13:43:37 · 题解

大蒟蒻来袭！

此题解有点长，请耐心观看

csp上1小时终于肝完了这道题（我太弱了）

Part1. 40分

#include<bits/stdc++.h>
using namespace std;
int l,sum;
struct subway{
    bool f;
    int t,p;
}tkt[100002];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        int x,a,b;
        cin>>x>>a>>b;
        if(!x){
            tkt[++l].p=a,tkt[l].t=b;
            sum+=a;
        }else{
            for(int j=1;j<=l;j++){
                if(!tkt[j].f&&tkt[j].p>=a&&b-tkt[j].t<=45){
                    sum-=a;
                    tkt[j].f=true;
                    break;
                }
            }
            sum+=a;
        }
    }
    cout<<sum;
    return 0;
}

40分钟，终于做完了QWQ。

但做的过程中总感觉可以加优化，但因太懒，没写

前2个小数据过了后，

发现——第三个大数据过不了(出题人太良心，给了三个数据)

Part 2. 10分

想好优化后，又打了一段：

while(b-tkt[top].t>45){
    top++;
}

终于第3个也过了。

Part 3. 100分

但这样的优化就一定对了吗？

考试时，我自己又出了一个样例。

咦？怎么与我自己算的不一样？

突然发现，好像有时不会进行选票。

数组爆界了！

将优化加特判后，终于对了

AC CODE：

#include<bits/stdc++.h>
using namespace std;
int l,top=1,sum;
//结构体，计票 
struct subway{
    bool f;
    int t,p;
}tkt[100002];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        int x,a,b;
        cin>>x>>a>>b;
        if(!x){  //如果x为0 
            tkt[++l].p=a,tkt[l].t=b;
            sum+=a; //地铁票一定得买 
        }else{
            //从top开始循环 
            for(int j=top;j<=l;j++){
                //如有符合条件的票 
                if(tkt[j].f&&tkt[j].p>=a&&b-tkt[j].t<=45){
                    sum-=a;
                    tkt[j].f=true;
                    break;
                }
            }
            sum+=a;
        }
        //重中之重，优化，将过时了的票排除。 
        while(b-tkt[top].t>45&&top<l){
            top++;
        }
    }
    //输出 
    cout<<sum;
    return 0;
}