本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷AT_abc465_b [ABC465B] Parking 2【题目描述】有一个停车场收费规则如下在从L LL点整到R RR点整的时间段内每停车一小时收费X XX。在上述时间段以外每停车一小时收费Y YY。如果一辆车从A AA点整停车到B BB点整并且没有跨越午夜请问应该收取多少停车费【输入】从标准输入读取格式如下X XXY YYL LLR RRA AAB BB【输出】输出答案。【输入样例】700 300 9 17 7 21【输出样例】7400【核心思想】问题分析给定高峰时段[ L , R ] [L, R][L,R]每小时收费X XX非高峰时段每小时收费Y YY停车时段[ A , B ] [A, B][A,B]不跨午夜。求总停车费。这是一个区间覆盖 分段计费问题核心在于将一天24 2424小时按高峰/非高峰分类再对停车时段逐小时累加。算法选择逐小时标记法用数组t [ i ] t[i]t[i]记录第i ii小时i ii点到i 1 i1i1点的收费标准先标记高峰时段再对停车时段逐小时累加关键步骤读入数据读取X , Y , L , R , A , B X, Y, L, R, A, BX,Y,L,R,A,B初始化费率数组i ii从1 11到23 2323t [ i ] ← Y t[i] \leftarrow Yt[i]←Y非高峰标记高峰时段i ii从L LL到R − 1 R-1R−1t [ i ] ← X t[i] \leftarrow Xt[i]←X累加停车费i ii从A AA到B − 1 B-1B−1a n s ← a n s t [ i ] ans \leftarrow ans t[i]ans←anst[i]输出结果a n s ansans时间/空间复杂度时间复杂度O ( 1 ) O(1)O(1)固定24 2424小时的遍历空间复杂度O ( 1 ) O(1)O(1)固定大小的费率数组逐小时标记与累加的核心思想离散时间建模将连续时间离散化为24 2424个整点区间第i ii小时代表时间段[ i , i 1 ) [i, i1)[i,i1)便于数组索引和逐小时计费高峰时段的数组标记t [ L ] t[L]t[L]到t [ R − 1 ] t[R-1]t[R−1]标记为X XX因为L LL点整到R RR点整包含的小时段是[ L , L 1 ) , [ L 1 , L 2 ) , … , [ R − 1 , R ) [L, L1), [L1, L2), \ldots, [R-1, R)[L,L1),[L1,L2),…,[R−1,R)共R − L R-LR−L个区间停车时段的对齐停车从A AA点整到B BB点整包含的小时段是[ A , A 1 ) , … , [ B − 1 , B ) [A, A1), \ldots, [B-1, B)[A,A1),…,[B−1,B)对应数组下标A AA到B − 1 B-1B−1不跨午夜的简化题目保证不跨午夜因此停车时段[ A , B ] [A, B][A,B]完全落在1 11到24 2424范围内无需处理日期边界适用于基础区间覆盖、分段计费、时间离散化类入门问题【算法标签】#入门 #模拟【代码详解】#includebits/stdc.husingnamespacestd;intx,y,l,r,a,b;// x: 高峰时段每小时费用; y: 非高峰时段每小时费用// l, r: 高峰时段起止时间; a, b: 停车起止时间intt[30];// t[i]: 第 i 小时i点到i1点的收费标准intmain(){cinxylrab;// 读入所有参数for(inti1;i23;i)// 初始化所有时段费用为 y非高峰t[i]y;for(intil;ir;i)// 将 l 到 r-1 时段的费用设为 x高峰t[i]x;intans0;// ans: 累计总停车费for(intia;ib;i)// 累加停车时段 a 到 b-1 的每小时费用anst[i];coutansendl;// 输出总停车费return0;}【运行结果】700 300 9 17 7 21 7400