题解:#2084.「CSP-J 2019」公交换乘 审核通过

lyhmbr CSP-J2二等 2024-07-19 14:45:51 2024-07-19 17:00:44 17

题目大意

给定你乘车方式,时间,价格 在乘坐地铁时即可优惠

乘坐公交时

  • 时间差

  • 价格低于地铁的票价

即可免费

解题思路(错的

定义一个结构体 分别记录 乘车的价格 时间 优惠

结构体代码

struct node{
    int w; //方式
    int pr; //价格
    int t; //时间
}node[2020];

然后用队列分别存储优惠的编号

队列是输入完在初始化的

初始化函数:

void init(int n){
    //将乘地铁的方式逆序排列
    //为了先使用使用过了的优惠卷
    for(int i = n ; i >= 1 ; i--){
        if(node[i].w == 0) s.push(i);
    }
}

在进行免费的判断 判断的函数

//判断是否免费
bool is_free(int n){
    if(node[n].w != 1) return false; //不是公交车
    //从对头开始判断,是的就返回true不是就pop,直到队为空
    if(s.empty()) return false; //卷用完了
    //if(node[s.front()].t > node[n].t) return false; //特判防止使用未来的卷
    //if(n == s.top())
    while(!s.empty()){
        //cout<<"is"<<endl;
        if(node[n].t - node[s.front()].t <= 45 && node[n].pr <= node[s.front()].pr ){ //可以使用卷
            cout<<"在node"<<n<<"使用了"<<s.front()<<"的卷"<<endl;
            s.pop(); //用完了卷就弹出
            return true;
        }else if (node[n].pr > node[s.front()].pr){ //超时的情况弹出最旧的
            s.pop();
        }else{
        }
    }
    return false;//没找到卷
    
}

错误的代码

//栈的方法不可行,还是用队列好了

#include <bits/stdc++.h>
#include <queue>
#include <stack>
using namespace std;

struct node{
    int w; //方式
    int pr; //价格
    int t; //时间
}node[2020];

queue<int> s;

//判断是否免费
bool is_free(int n){
    if(node[n].w != 1) return false; //不是公交车
    //从对头开始判断,是的就返回true不是就pop,直到队为空
    if(s.empty()) return false; //卷用完了
    //if(node[s.front()].t > node[n].t) return false; //特判防止使用未来的卷
    //if(n == s.top())
    while(!s.empty()){
        //cout<<"is"<<endl;
        if(node[n].t - node[s.front()].t <= 45 && node[n].pr <= node[s.front()].pr ){ //可以使用卷
            cout<<"在node"<<n<<"使用了"<<s.front()<<"的卷"<<endl;
            s.pop(); //用完了卷就弹出
            return true;
        }else if (node[n].pr > node[s.front()].pr){ //超时的情况弹出最旧的
            s.pop();
        }else{
        }
    }
    return false;//没找到卷
    
}

void init(int n){
    //将乘地铁的方式逆序排列
    //为了先使用使用过了的优惠卷
    for(int i = n ; i >= 1 ; i--){
        if(node[i].w == 0) s.push(i);
    }
}

void add(int n){
    s.push(n);
}

void PRINT(int n){ //debug函数,用来看栈内的元素的
    while (!s.empty()) {
        cout<<"编号 "<<s.front()<<" 内容 "<<node[s.front()].t<<"时间"<<endl;
        s.pop();
    }
    init(n);
}

int main(){
    int n;
    cin>>n;
    for(int i = 1 ; i <= n ;i++){
        cin>>node[i].w>>node[i].pr>>node[i].t;
    } //输入
    init(n);//初始化
    PRINT(n);
    int price = 0;
    //开始计费
    for(int i = 1 ; i <= n ; i++){
        add(i);
        if(is_free(i)) {
            continue;
        }//免费的情况
        price += node[i].pr;
        //cout<<"main"<<endl;
    }
    cout<<price;
}

错误分析

我的免单队列是先输入在初始化的,导致 函数的内容变得十分复杂才导致了 的错误

错误改正

那么那份错误的代码有什么可以参考的部分呢?

  1. 结构体来存储输入的数据
  2. is_free函数
  3. main函数的大体结构

那有什么要改的呢

  1. 用队列来存储优惠卷
  2. init函数应去掉
  3. 优惠应改成实时的可以使is_free函数变得简单

AC代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1000007;

//用结构体
struct node {
    int pr , way , time;
    // 价格  方式  时间
}p[N];

int ans;
int tim[N],sum;
int pri[N];
//tim 记录时间
//pri 记录价钱

void is_free(int i){//查看是否免费
    int flag = -1;
    for(int j = sum ;p[i].time-tim[j]<=45 && j>=1; j--){//逆序寻找避免无效遍历
        if(pri[j] >= p[i].pr){
            flag = j; //免费
        }
    }
    if(flag == -1){//没找到付钱
        ans += p[i].pr;
    }else{//找到了
        pri[flag] = 0; //设为0则无法通过判断
    }
}

int main(){
    int n ;
    cin>>n;
    //数据输入
    for(int i = 1 ; i <= n ; i++){
        cin>>p[i].way>>p[i].pr>>p[i].time;
        //坐公交必须付钱
        if(p[i].way == 0){
            ans += p[i].pr;
            tim[++sum] = p[i].time;
            //按顺序放入坐公交时的时间和价钱
            pri[sum] = p[i】。pr;
        }else{//坐地铁考虑免费
            is_free(i)//进行判断是否免费
        }
    }
    cout<<ans;

}

{{ vote && vote.total.up }}

共 3 条回复

lyh046 蔚蓝档案

lyhmbr CSP-J2二等

改了标点符号防止直接复制

lyh046 蔚蓝档案

《AC代码》