3 solutions

  • 2
    @ 2021-6-7 18:06:35

    分析题意:

    • 如果乘坐地铁,则需完全付费;
    • 如果乘坐公交,有可用优惠券时无需付费,而无可用优惠券时需完全付费;
    • 优惠券可用的条件:
      1. 公交车价格低于优惠券价格;
      2. 公交车在45分钟以内乘坐;
      3. 优惠券未被使用。

    基于此,考虑用结构体存储每一张优惠券。

    struct coupon {
        int price; //优惠券价格
        int t; //优惠券时间
        bool used; //优惠券是否已经使用
    } coupons[100005];
    

    对于每一次输入,模拟获得优惠券和使用优惠券的过程。

    考虑到乘车记录的时间以递增形式给出,可以进行优化:若一张优惠券已经超时了,那么优惠券一定不再可用。

    /* 部分变量的说明:
    (1)N表示优惠券总张数;
    (2)ans表示答案,即花费的总价格;
    (3)st表示每次枚举优惠券的起始下标。
    */
    for (int i = 1; i <= n; i++) {
            int trans, price, t;
            scanf("%d%d%d", &trans, &price, &t);
            if (trans == 1) {
                //尝试使用优惠券
                bool flag = false;
                for (int i = st; i <= N; i++) {
                    //检查优惠券是否可用
                    if (t - coupons[i].t > 45)
                        st = i + 1; //优惠券超时了就永远不再可用
    
                    if (t - coupons[i].t <= 45 && price <= coupons[i].price && !coupons[i].used) {
                        coupons[i].used = true;
                        flag = true;
                        break;
                    }
                }
    
                if (!flag)
                    ans += price;
            } else {
                ans += price;
                coupon cou;
                cou.price = price;
                cou.t = t;
                cou.used = false;
                coupons[++N] = cou; //添加一张优惠券
            }
        }
    
    • 1
      @ 2022-6-12 10:18:04
      #include<bits/stdc++.h>
      using namespace std;
      int opt,n,t[100001],p[100001],ans,top,m=1,yh[100001],sj[100001],k;
      bool r[100001];
      int main(){
      	cin>>n;
      	for(int i=1;i<=n;i++){
      		cin>>opt>>p[i]>>t[i];
      		if(opt==0) yh[++top]=p[i],sj[top]=t[i],ans+=p[i];
      		else{
      			k=0;
      			for(int j=m;j<=top;j++){
      				if(r[j]) continue;
      				if(t[i]-sj[j]>45) m=j;
      				else if(yh[j]>=p[i]){
      					k=j;
      					r[k]=true;
      					break;
      				}
      			}
      			if(!k) ans+=p[i];
      		}
      	}///test
      	cout<<ans;
      }
      
      • 1
        @ 2022-3-14 0:01:30

        向大家隆重介绍 STL 的 List !

        #include <bits/stdc++.h>
        using namespace std;
        
        int n, type, price, t, total;
        struct Ticket {
            int price, t;
        };
        list<Ticket> tickets;
        
        int main() {
            cin >> n;
            for (int i = 1; i <= n; i++) {
                cin >> type >> price >> t;
                if (type == 0) {
                    // 如果是地铁,那么新建一张优惠券,并付钱
                    tickets.push_back({ price, t });
                    total += price;
                } else {
                    bool found = false;
                    // 扔掉过期的
                    while (tickets.size() && t - tickets.front().t > 45) tickets.pop_front();
                    // 查找符合要求的
                    for (auto it = tickets.begin(); it != tickets.end(); ++it) {
                        if (it->price >= price) {
                            tickets.erase(it);
                            found = true;
                            break;
                        }
                    }
                    // 没找到就付钱
                    if (!found) total += price;
                }
            }
            cout << total << endl;
            return 0;
        }
        
        • 1

        Information

        ID
        118
        Time
        1000ms
        Memory
        256MiB
        Difficulty
        5
        Tags
        # Submissions
        118
        Accepted
        46
        Uploaded By