本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P10188 [USACO24FEB] Milk Exchange B - 洛谷【题目描述】Farmer John 的N NN1 ≤ N ≤ 2 ⋅ 10 5 1\le N\le 2\cdot 10^51≤N≤2⋅105头奶牛排成一圈使得对于1 , 2 , … , N − 1 1,2,\ldots,N−11,2,…,N−1中的每个i ii奶牛i ii右边的奶牛是奶牛i 1 i1i1而奶牛N NN右边的奶牛是奶牛1 11。第i ii头奶牛有一个容量为整数a i a_iai1 ≤ a i ≤ 10 9 1\le a_i\le 10^91≤ai≤109升的桶。所有桶初始时都是满的。每一分钟奶牛都会根据一个字符串s 1 s 2 … s N s_1s_2\ldots s_Ns1s2…sN传递牛奶该字符串仅由字符L和R组成。当第i ii头奶牛至少有1 11升牛奶时如果s i L s_i\texttt{L}siL她会将1 11升牛奶传递给她左边的奶牛如果s i R s_i\texttt RsiR则传递给右边的奶牛。所有交换同时发生即如果一头奶牛的桶是满的送出一升牛奶但也收到一升则她的牛奶量保持不变。如果此时一头奶牛的牛奶量超过a i a_iai则多余的牛奶会损失。FJ 想要知道经过M MM分钟1 ≤ M ≤ 10 9 1\le M\le 10^91≤M≤109后所有奶牛总共还余下多少牛奶【输入】输入的第一行包含N NN和M MM。第二行包含一个字符串s 1 s 2 … s N s_1s_2\ldots s_Ns1s2…sN仅由字符L或R组成表示每头奶牛传递牛奶的方向。第三行包含整数a 1 , a 2 , … , a N a_1,a_2,\ldots,a_Na1,a2,…,aN为每个桶的容量。【输出】输出一个整数为M MM分钟后所有奶牛总共余下的牛奶量。注意这个问题涉及到的整数可能需要使用 64 位整数型例如C/C 中的long long。【输入样例】3 1 RRL 1 1 1【输出样例】2【核心思想】问题分析N NN头奶牛围成一圈每头奶牛有容量a i a_iai的桶初始全满。每分钟所有奶牛同时按照方向字符串s ssL向左R向右传递 1 升牛奶若自己有奶同时可能收到 1 升。若某头牛收到后超过容量溢出损失。求经过M MM分钟M ≤ 10 9 M \le 10^9M≤109后所有桶中剩余牛奶总量。关键洞察由于传递是同时且同步的且每头牛每轮至多给出 1 升、收到 1 升因此只有方向模式中出现R后紧接L即RL的位置才会产生溢出。因为牛奶会沿R方向汇聚再沿L方向汇聚最终在RL交界处堆积并溢出。其余位置的牛奶只是在循环流动不会损失若首尾衔接的L...R模式则因为围成环会形成稳定流无净损失。因此只需找出所有RL交界点计算每个交界点在M MM分钟内损失的牛奶量从初始总量中扣除。算法选择模拟 数学不逐分钟模拟而是分析“溢出结构”。每个RL交界点奶牛i ii方向为R奶牛( i 1 ) m o d N (i1)\bmod N(i1)modN方向为L$会成为一个“汇点”左右两侧连续同向的奶牛会向该汇点输送牛奶。经过 $t$ 分钟从汇点左侧的连续R段和右侧的连续L段中每头牛会向汇点方向输送 $t$ 升牛奶但受限于自身容量。因此每个RL结构的溢出量为左侧连续R段所有奶牛的 $\min(a_j, M)$ 之和 右侧连续L段所有奶牛的 $\min(a_j, M)$ 之和再与 $M$ 取较小值因为每分钟该结构最多溢出 1 升。总损失为所有RL 结构损失之和。关键步骤基于代码逻辑读入N , M N, MN,M方向字符串s ss容量数组a i a_iai。计算初始总量ans sum(a_i)。标记溢出结构遍历i ii从 0 到N − 1 N-1N−1若s [ i ] ′ R ′ s[i] Rs[i]′R′且s [ ( i 1 ) % N ] ′ L ′ s[(i1)\%N] Ls[(i1)%N]′L′则标记L[i] true该位置是结构起点即R的位置和R[(i1)%N] true该位置是结构终点即 L$ 的位置。计算每个结构的溢出损失若L[i] true即位置i ii是某个RL中的R则向左逆时针扫描连续R段累加该段所有奶牛的min ( a j , M ) \min(a_j, M)min(aj,M)到sum。若R[i] true$即位置 $i$ 是某个RL中的L则向右顺时针扫描连续L段累加该段所有奶牛的 $\min(a_j, M)$ 到sum。从ans中减去min(sum, (long long)M)因为每个结构每分钟最多溢出 1 升。输出ans。时间/空间复杂度时间复杂度O ( N ) O(N)O(N)线性扫描并处理连续段。空间复杂度O ( N ) O(N)O(N)存储数组和标记。模拟 数学的核心思想识别稳定流在环形排列中方向相同的连续段形成“流”。只有R段后接L段的位置RL边界会产生牛奶堆积和溢出因为牛奶从两侧流向该边界。相反L后接R的边界 (LR) 会产生分流不会溢出。每轮损失上限每个RL边界每分钟最多损失 1 升牛奶因为只有边界处的牛会收到来自两边的各 1 升而自身给出 1 升净增 1 升若已满则溢出 1 升。因此总损失 边界数 × 时间但受限于各段奶牛的总容量因为如果某段奶牛被掏空则不再有牛奶流向边界。处理容量限制对于左侧R段每头牛j jj在M MM分钟内最多贡献min ( a j , M ) \min(a_j, M)min(aj,M)升牛奶因为每分钟输出 1 升a j a_jaj升后自桶空。右侧L段同理。因此边界可损失的总量为这些贡献之和与M MM取较小值。适用场景适用于环形同步传输、容量有限、问长时间后总量损失的模拟问题。核心是找出“汇聚点”并利用时间与容量的最小值计算损失。【解题思路】【算法标签】#普及 #数学【代码详解】#includebits/stdc.husingnamespacestd;intn,m;longlonga[200005],ans;string s;boolL[200005],R[200005];//L[i]true表示点i为某个溢出结构的起点//R[i]true表示点i为某个溢出结构的终点intmain(){cinnm;cins;for(inti0;in;i){cina[i];ansa[i];}//第一步从左到右找出字符串s中所有的溢出结构RL并标记其起点和终点for(inti0;in-1;i){if(s[i]Rs[(i1)%n]L){L[i]true;R[(i1)%n]true;}}//第二步从左到右计算每个溢出结构导致的牛奶溢出for(inti0;in;i){longlongsum0;// 每个溢出结构溢出的牛奶数量if(L[i]true){// i号桶为某个溢出结构的起点intj(i-1n)%n;// 记录i号桶左边的编号jwhile(s[j]R){suma[j];j(j-1n)%n;// 继续向左}}if(R[i]true){// i号桶为某个溢出结构的终点intj(i1)%n;// 记录i号桶右边的编号jwhile(s[j]L){suma[j];j(j1)%n;// 继续向右}}ans-min(sum,(longlong)m);}coutansendl;return0;}【运行结果】3 1 RRL 1 1 1 2