1 条题解
-
0
C++ :
#include<bits/stdc++.h> using namespace std; /* 维护45分钟的滑动窗口(队列实现),来存储当前可用的优惠券: 1、如果是当前是地铁票,先买票,然后将优惠券存入滑动窗口; 2、如果当前是公交车: 从滑动窗口中,找出第1个没有被用过的,且金额>=当前票价的优惠券; 找到:标记该优惠券使用; 没找到:只能买票! */ const int N = 100010; int n; struct ticket{ int time,price;//时间,价格 bool used;//该票是否使用 }tk[N]; int main() { scanf("%d",&n); int l = 0,r = 0;//头尾指针 int res = 0; int type,price,time; for(int i = 0;i < n;i++){ scanf("%d%d%d",&type,&price,&time); //如果是乘坐地铁 if(type == 0){ res = res + price; //存储优惠券 tk[r].time = time; tk[r].price = price; r++; } else{ //弹出所有不在区间内的票 while(l < r && time - tk[l].time > 45) l++; bool f = false;//假设没找到可用的优惠券 for(int i = l;i < r;i++){ //如果有优惠券没有用过,且价格超过当前的票价 if(tk[i].used==false && tk[i].price >= price){ tk[i].used = true; f = true; break; } } //如果没有优惠券,买票 if(!f) res += price; } } //输出票价 printf("%d\n",res); return 0; }
- 1
信息
- ID
- 853
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 上传者