首页 > 其他分享 >CSP-J2019公交换乘

CSP-J2019公交换乘

时间:2024-08-01 09:42:56浏览次数:19  
标签:used int price pop cost time J2019 换乘 CSP

马上CSP2024了,做题ing... (

题目描述

戳它

思路

1.用结构体双端队列存票,用双端队列的原因是后面要遍历
2.结构体元素:price+time+used
3.过期的票要及时pop
4.不要一边遍历一边pop,用used标记

代码

#include <bits/stdc++.h>
using namespace std;
struct Ticket {
    int price, time;
    bool used;
};
deque<Ticket> q;
int n, cost;
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int op, price, time;
        cin >> op >> price >> time;
        if (op == 0) {
            cost += price;
            q.push_back({price, time + 45, false});
        } else {
            while (!q.empty() && q.front().time < time) q.pop_front();
            bool f = false;
            for (int j = 0; j < (int)q.size(); ++j) {
                if (q[j].price >= price && q[j].used == 0) {
                    f = true;
                    q[j].used = 1;
                    break;
                }
            }
            if (!f) cost += price;
        }
    }
    cout << cost;
    return 0;
}

祝点赞的各位dalao AK IOI!

标签:used,int,price,pop,cost,time,J2019,换乘,CSP
From: https://www.cnblogs.com/algorithm-hu/p/18335970

相关文章

  • 暑假集训CSP提高模拟12
    T1这题千万不要认为是莫反题枚举质因子\(x,y\),\(x,y<=998\),对答案的贡献为\(min(\lfloor{\frac{B}{x}}\rfloor,\lfloor{\frac{D}{y}}\rfloor)\),再容斥一下即可MD最后答案要取模啊点击查看代码#include<bits/stdc++.h>#definespeed()ios::sync_with_stdio(false),cin.t......
  • 『模拟赛』暑假集训CSP提高模拟12
    Rank正常偏下发挥吧。A.黑客签到题。题目中的关键点是只有\(x\)和\(y\)的和在区间\(\left[0,999\right]\)内才合法,因此我们只枚举和在这个范围内的两个值,寻找约分前的值即可,复杂度为\(\mathcal{O(999^2)}\)。点击查看代码#include<bits/stdc++.h>#definefo(x,......
  • 暑假集训CSP提高模拟12
    暑假集训CSP提高模拟12\(T1\)P171.黑客\(40pts\)将式子进行二维差分。考虑枚举\(\frac{i+j}{\gcd(i,j)}=t\),并统计它能对答案产生的贡献。令\(\gcd(i,j)=1\),这样的话才会不重不漏。推式子,有\(\begin{aligned}&\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}[\fr......
  • 暑假集训CSP提高模拟 ∫[0,6] (x^2)/6 dx
    \[\text{暑假集训CSP提高模拟}\int^{6}_{0}\frac{x^{2}}{6}dx\]A.黑客显然这个题里只有\(999\)放在复杂度里是有可能对的,要么是\(999^{2}\)要么是\(999^{2}\log999\),显然应该是前者.考虑枚举全部的最简分数,然后乘上去,算的时候直接算当前分母/分子是最简分式的几倍(注意上......
  • 暑假集训csp提高模拟12
    赛时rank47,T1100,T20,T30,T420做题策略不好,没做T2,死在T4上了。感觉赛时就是唐。T1黑客考虑枚举结果,如果存在贡献,那么一定有\(i+j=k\&gcd(i,j)=1\),统计一下有多少组即可点此查看代码#include<bits/stdc++.h>#include<bits/extc++.h>//usingnamespace__gnu_pbds;......
  • CSP模拟10--总结
    今天是我第一次给模拟赛写正规总结--因为今天的题真的受不了了四道数学题,一点都不拖泥带水的纯血数学题!T1、黑暗型高松灯shit本来是一道放在T4防AK的题,结果学长为了恶心锻炼一下我们,直接将T1和T4swap了一下.一开始看了半个小时挺懵逼的,然后跳了,但心里一直觉得这题能做......
  • 7月30日CSP-S模拟赛赛后总结
    7月30日模拟赛赛后总结\[7月30日\\模拟赛\\赛后总结\\2024年7月30日\\by\\\hcy\]洛谷同步:点我一、做题情况第一题比赛\(100pts\),赛后\(AC\)第二题比赛\(20pts\),赛后\(AC\)第三题比赛\(0pts\),赛后\(AC\)第四题比赛\(30pts\),赛后\(30pts\)......
  • CSP 初赛复习 :计算机系统原理
            计算机系统是一个复杂的电子机器,‌它能够按照程序运行,‌自动、‌高速处理海量数据。‌这个系统主要由硬件系统和软件系统组成。‌硬件系统包括各种物理组件,‌如处理器、‌内存、‌存储设备等,‌而软件系统则包括操作系统、‌应用程序和其他必要的软件。‌硬件......
  • 「模拟赛」暑期集训CSP提高模拟10(7.28)
    \(145pts,Rank10\),众数分。数学专题模拟赛%%%总结写前面:1.线性递推式复杂度过大考虑矩阵快速幂优化;2.T1长时间切不了就先跳,先把所有题看一遍,拿分为主。赛时记录正常开T1,期望数学题,大概读懂了,手模下小样例,模了一遍又一遍,“我并不认为样例是对的”,跳了(很正确的决定)。......
  • 暑假集训csp提高模拟11
    赛时rank9,T1100,T2100,T30,T40update:赛后T1被hack了,成了99,死因没有记忆化挂成了rank10我又要挂分了。T3暴力挂了?话说jjdw和k8啥时候回来。T1Fate签到题,最短路板子。考虑一个点\(a\),其最短路前驱节点为\(b\),前驱结点组成的集合为\(B\),其次短路的前驱节点为......