deque解法
2025-07-17 11:01:16
发布于：北京
194阅读
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;//好习惯不要忘
}
全部评论 8
#include <iostream> #include <queue> #include <vector> using namespace std; class node { public: int price, time; bool operator<(const node& other) const { return time > other.time; } }; int main() { int n; cin >> n; priority_queue<node> q; long long sum = 0; for (int i = 1; i <= n; i++) { int a, b, c; cin >> a >> b >> c; vector<node> v; while (!q.empty()) { auto f = q.top(); q.pop(); if (c - f.time > 45) { continue; } else { v.push_back({f.price, f.time}); } } for (auto i : v) { q.push({i.price, i.time}); } if (a == 0) { q.push({b, c}); sum += b; } else { bool flag = 0; vector<node> v; while (!q.empty()) { auto f = q.top(); q.pop(); if (f.price >= b) { flag = 1; break; } else { v.push_back({f.price, f.time}); } } for (auto i : v) { q.push({i.price, i.time}); } if (flag == 0) { sum += b; } } } cout << sum; return 0; }其实也可以使用优先队列，我这个也是暴力写法，主要还是数据比较温和，所以说能过。正解应该是使用桶排
2026-06-14 来自 广东
0
有帮助，赞一个