题目大意
给定你乘车方式，时间，价格 在乘坐地铁时即可优惠
乘坐公交时
-
时间差
-
价格低于地铁的票价
即可免费
解题思路（错的
定义一个结构体 分别记录 乘车的价格 时间 优惠
结构体代码
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;
}
错误分析
我的免单队列是先输入在初始化的，导致 函数的内容变得十分复杂才导致了 和 的错误
错误改正
那么那份错误的代码有什么可以参考的部分呢？
- 结构体来存储输入的数据
is_free函数main函数的大体结构
那有什么要改的呢
- 用队列来存储优惠卷
init函数应去掉- 优惠应改成实时的可以使
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；
}