1 条题解
-
1
#include <bits/stdc++.h> using namespace std; /* 有多张优惠票满足条件, 则优先消耗获得最早的优惠票 1.坐地铁 买票 获得等额的优惠券:金额、获得时间、是否使用过 2.坐公交 在有效期内的优惠券中,查找第1张金额>=公交票价的优惠券 找到:使用该优惠券 找不到:买票 使用队列,维护优惠券的信息 */ const int N = 1e5 + 10; struct node{ int price,time; bool used; }q[N];//优惠券的队列 int h = 1,t = 0; int n,ans = 0; int main(){ scanf("%d",&n); int type,money,start; for(int i = 1;i <= n;i++){ scanf("%d%d%d",&type,&money,&start); //如果是地铁 if(type == 0){ //买票,获得优惠券 ans += money; t++; q[t].price = money; q[t].time = start; q[t].used = false;//默认没有使用 }else{ //公交 //丢弃过期的优惠期 while(h<=t&&start-q[h].time>45) h++; bool f = false;//假设没找到 //在有效期内的优惠券,找第一张>=公交票价的 且 没有用过的优惠券 for(int j = h;j <= t;j++){ if(q[j].price >= money && q[j].used == false){ q[j].used = true; f = true; break; } } //如果没有找到能用的优惠券,买票 if(f == false) ans += money; } } printf("%d",ans); return 0; }
- 1
信息
- ID
- 291
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 5
- 标签
- 递交数
- 149
- 已通过
- 56
- 上传者