deque解法
2025-07-17 11:01:16
发布于:北京
25阅读
0回复
0点赞
一种偏暴力的解法,欢迎大佬指正。其实是没想出来单队列解法555
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
deque<pair<int,int> > a;//存优惠
deque<pair<int,int> > b;//临时存储钱不够但时间不超过45的票
int cnt=0;//总花费
for (int i=1;i<=n;i++)
{
int x,y,z;//输入
cin>>x>>y>>z;
bool f=0;//判断用没用优惠券
if (x==0)//坐地铁
{
a.push_back({y,z});//存优惠券
cnt+=y;//花钱
}
else
{
while(!a.empty())//找有没有优惠券能用
{
if (z-a.front().second<=45 && y<=a.front().first)//能用
{
a.pop_front();//用掉了
f=1;//用优惠券
break;
}
else if(z-a.front().second<=45 && y>a.front().first)//钱不够但时间没超
{
b.push_back(a.front());//临时存
a.pop_front();
}
else
{
a.pop_front();//时间超了,直接扔掉
}
}
while(!b.empty())//刚才钱不够但时间够的重新存回去
{
a.push_front(b.back());
b.pop_back();
}
if (!f)
{
cnt+=y;//如果没用优惠券就花钱
}
}
}
cout<<cnt;
return 0;//好习惯不要忘
}
全部评论 7
顶
5天前 来自 河北
0顶
5天前 来自 河北
0顶
5天前 来自 河北
0顶
5天前 来自 河北
0顶
5天前 来自 河北
0顶
5天前 来自 河北
0%%%
5天前 来自 河北
0
有帮助,赞一个