企业官网建设流程全解析

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

洛谷：P10188 [USACO24FEB] Milk Exchange B - 洛谷

【题目描述】

Farmer John 的N NN（1 ≤ 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 i+1i+1，而奶牛N NN右边的奶牛是奶牛1 11。第i ii头奶牛有一个容量为整数a i a_iai​（1 ≤ a i ≤ 10 9 1\le a_i\le 10^91≤ai​≤109）升的桶。所有桶初始时都是满的。

每一分钟，奶牛都会根据一个字符串s 1 s 2 … s N s_1s_2\ldots s_Ns1​s2​…sN​
传递牛奶，该字符串仅由字符L和R组成。当第i ii头奶牛至少有1 11升牛奶时，如果s i = L s_i=\texttt{L}si​=L，她会将1 11升牛奶传递给她左边的奶牛，如果s i = R s_i=\texttt Rsi​=R则传递给右边的奶牛。所有交换同时发生（即，如果一头奶牛的桶是满的，送出一升牛奶，但也收到一升，则她的牛奶量保持不变）。如果此时一头奶牛的牛奶量超过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_Ns1​s2​…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

【核心思想】

1. 问题分析：N NN头奶牛围成一圈，每头奶牛有容量a i a_iai​的桶，初始全满。每分钟，所有奶牛同时按照方向字符串s ss（L向左，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分钟内损失的牛奶量，从初始总量中扣除。

2. 算法选择：

   • 模拟 + 数学：不逐分钟模拟，而是分析“溢出结构”。每个RL交界点（奶牛i ii方向为R，奶牛( i + 1 ) m o d N (i+1)\bmod N(i+1)modN方向为L$）会成为一个“汇点”，左右两侧连续同向的奶牛会向该汇点输送牛奶。经过 $t$ 分钟，从汇点左侧的连续R段和右侧的连续L段中，每头牛会向汇点方向输送 $t$ 升牛奶（但受限于自身容量）。因此，每个RL结构的溢出量为：左侧连续R段所有奶牛的 $\min(a_j, M)$ 之和 + 右侧连续L段所有奶牛的 $\min(a_j, M)$ 之和，再与 $M$ 取较小值（因为每分钟该结构最多溢出 1 升）。总损失为所有RL` 结构损失之和。

3. 关键步骤（基于代码逻辑）：

   • 读入：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] == 'R's[i]==′R′且s [ ( i + 1 ) % N ] = = ′ L ′ s[(i+1)\%N] == 'L's[(i+1)%N]==′L′，则标记L[i] = true（该位置是结构起点，即R的位置）和R[(i+1)%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。

4. 时间/空间复杂度：

   • 时间复杂度：O ( N ) O(N)O(N)，线性扫描并处理连续段。
   • 空间复杂度：O ( N ) O(N)O(N)，存储数组和标记。

5. 模拟 + 数学的核心思想：

   • 识别稳定流：在环形排列中，方向相同的连续段形成“流”。只有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取较小值。
   • 适用场景：适用于环形同步传输、容量有限、问长时间后总量损失的模拟问题。核心是找出“汇聚点”，并利用时间与容量的最小值计算损失。

【解题思路】

【算法标签】

#普及+ #数学

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;intn,m;longlonga[200005],ans;string s;boolL[200005],R[200005];//L[i]=true表示点i为某个溢出结构的起点//R[i]=true表示点i为某个溢出结构的终点intmain(){cin>>n>>m;cin>>s;for(inti=0;i<n;i++){cin>>a[i];ans+=a[i];}//第一步：从左到右找出字符串s中所有的溢出结构RL，并标记其起点和终点for(inti=0;i<=n-1;i++){if(s[i]=='R'&&s[(i+1)%n]=='L'){L[i]=true;R[(i+1)%n]=true;}}//第二步：从左到右计算每个溢出结构导致的牛奶溢出for(inti=0;i<n;i++){longlongsum=0;// 每个溢出结构溢出的牛奶数量if(L[i]==true){// i号桶为某个溢出结构的起点intj=(i-1+n)%n;// 记录i号桶左边的编号jwhile(s[j]=='R'){sum+=a[j];j=(j-1+n)%n;// 继续向左}}if(R[i]==true){// i号桶为某个溢出结构的终点intj=(i+1)%n;// 记录i号桶右边的编号jwhile(s[j]=='L'){sum+=a[j];j=(j+1)%n;// 继续向右}}ans-=min(sum,(longlong)m);}cout<<ans<<endl;return0;}

【运行结果】

3 1 RRL 1 1 1 2