题解：T580827 欧冠附加赛
Doraeman
·
·
题解
知识点
本题考察前缀和与单调队列。
知识补充
OI WiKi 前缀和讲解。
OI WiKi 单调队列讲解。
P1886 滑动窗口 /【模板】单调队列；
P1886 滑动窗口 /【模板】单调队列 题解。
单调队列 博客 1；单调队列 博客 2；
单调队列 博客 3；单调队列 博客 4。
简化版题意
可以先求出曼城的每分钟的净胜球（“净胜球”知识科普）。
将题目转化为：扣除长度不超过 K 的一段区间内的曼城的全部净胜球，要求这个区间内曼城净胜球最小。因为曼城总净胜球固定不变，所以此时剩余的曼城净胜球最大。
注：如果所有符合要求的区间内曼城的净胜球都是正数，就不需要扣除任何区间，因为扣除后曼城总净胜球反而会减少。
形式化题意
由上述简化版题意，可以进一步得到形式化题意。
给定序列：
m=\{m_1,m_2,\dots,m_N\}，\\
r=\{r_1,r_2,\dots,r_N\}。
规定序列：
a=\{m_1-r_1,m_2-r_2,\dots,m_N-r_N\}。
设 S 为 a_{left+1} 到 a_{right} 求和。
当以下式子取到最小值时（此处使用 (left+1) 方便后续计算），
S=\sum_{i=left+1}^{right}a_i\ \ (0\leq right-(left+1)+1\leq K)
如果 S<0，求以下两个式子的最大值（S 可能有多个最小值，会对应不同的 left,right）。
\sum_{i=1}^{N}m_i-\sum_{i=left+1}^{right}m_i
\sum_{i=1}^{N}r_i-\sum_{i=left+1}^{right}r_i
注：经计算，这两个式子的差是 \sum_{i=1}^{N}a_i-S，在 S 确定时为定值，所以保证两式能同时取到最大值。
特别地，如果 S>0，直接求 \sum_{i=1}^{N}m_i 和 \sum_{i=1}^{N}r_i。
前缀和部分
观察上方的简化版题意和形式化题意，可以发现出现了多次“求和”，其中主要是求 m,r,a 序列的区间和。
如果直接使用循环遍历求区间和，总代码时间复杂度可能达到 \operatorname{O}(N^2)，最多获得 40 分。
如果使用前缀和 (1\leq i\leq N)：
经过前缀和计算，我们可以将之前的**求和式**全部转化为**前缀和数列中的某个数**。具体对应如下：
- $\sum_{i=1}^{N}a_i=A_N$；
- $\sum_{i=1}^{N}m_i=M_N$；
- $\sum_{i=1}^{N}r_i=R_N$；
- $S=A_{right}-A_{left}$。
注：此处要特别注意，$S=A_{right}-A_{left}$ 而非 $A_{right}-A_{left+1}$。这个式子与前缀和求区间和相关知识有关。
### 前缀和（预处理）代码
```cpp
// 进球前缀和
for(int i=0; i<n; i++)
M[i+1] = M[i] + (s[i] == 'M'),
R[i+1] = R[i] + (s[i] == 'R');
// 净胜球前缀和
for(int i=1; i<=n; i++)
a[i] = M[i] - R[i];
```
## 单调队列部分
求和问题解决后，我们迎来了第二大问题：**求所有 $S$ 的最小值**。
如果遍历所有符合条件的 $left,right$，时间复杂度达到 $\operatorname{O}(N^2)$，超时。
这时候就要用到**单调队列**了。
根据例题 P1886，我们可以了解到：**单调队列可以在 $\operatorname{O}(N)$ 时间复杂度内，求出数列中各个长度为 $K$ 的区间的最小值（或最大值）**。
### 知识点转化
只求到长度为 $K$ 的区间的最小值还不够，还有一步。
我们求的是 $S=A_{right}-A_{left}$ 的最小值。为了使 $S$ 最大，可以对于所有 $A_{right}$，都求出 $A_{left}$ 的**最大值**，**此时原式 $S$ 取到最小**。
### 单调队列·实现方法
遍历 $A$ 数列得到每个 $A_{right}=A_1,A_2,\dots,A_N$，并同时求以 $A_{right}$ 为结尾的长度最大为 $(K+1)$ 的区间内的最大值，作为 $A_{left}$。
即 $A_{left}=\min\{A_{right-K},A_{right-K+1},\dots,A_{right}\}$（此数列长度恰好为 $K$）。
注：整数 **$left$ 的取值区间的长度是 $(K+1)$ 而非 $K$。**
根据 $S$ 的式子，我们实际上要扣除 $A_{[left+1,right]}$ 这个区间，$left+1$ 的取值区间的长度是 $K$，且以 $right$ 结尾。
**使用区间长度计算公式（区间长度 $=$ 右边界 $-$ 左边界 $+1$）写成：$0\leq right-(left+1)+1\leq K$。
解得：$right-K\leq left\leq right$。**
使用双端队列 $q$，```q.front()``` 记录 $left$。
#### 移除出界元素
由前文，因为 $right-K\leq left\leq right$，所以，当 $left<right-K$ 时，我们就认定它“出界”，删除这个元素。
注 1：所有的 $left$ 都从各个 $right$ 之前的双端队列中获得，而 $right$ 从小到大考虑。不会出现 $left>right$ 的情况，故不考虑。
注 2：在 for 循环中，每次变量 $right$ 自增 $1$，与之对应的 $left$ 最多也就只会有 $1$ 个出界，所以写 if 即可，不用写 while。
于是我们就可以写：
```cpp
// 1.出队·移除出界元素
if(!q.empty() && left<right-K)
q.pop_front();
```
#### 维护单调递增
直接按照模板写。
```cpp
// 2.出队·维护单调递减
while(!q.empty() && A[i] >= A[q.back()])
q.pop_back();
```
#### 新元素加入
```c++
// 3.入队·新元素加入
q.push_back(i);
```
### 区间求和·记录最大值
对于每个 $A_{right}$，使用单调队列求得长度为 $K+1$ 的区间内最大的 $A_{left}$ 之后，求得到了当前 $S$ 的最小取值。
即：$S=A_{right}-A_{left}$。
用 $mini$ 记录 $S$（净胜球）的最小值，如果 $S<mini$，就更新 $mini$ 为 $S$，最后求出扣除的最小的曼城净胜球 $mini$。
如果这个最终值 $mini>0$，说明扣除的曼城净胜球最少也是正数，也就是说整场比赛对曼城都是有利的，不需要扣除任何区间，直接输出 $M_N,R_N$ 作为答案。
### 进球最大值
求出最优净胜球还没有结束。还有最后一步：在曼城净胜球最大的情况下，最大化曼城进球（也即最大化皇马进球）。
转变思路：最大化两队进球，即在 $S$ 为最小值时，最小化两队扣除的进球。
也可以写成：在 $S=A_{right}-A_{left}$ 为最小值时，最小化 $M_{goal}=M_{right}-M_{left}$ 和 $R_{goal}=R_{right}-R_{left}$。
更新这两个值需要分两种情况讨论：
1. 如果当前的 $S<mini$，此时新的 $S$ 一定更优。先考虑求 $S$ 的最小值，所以直接同步更新；
```cpp
Mgoal = M[right] - M[left];
Rgoal = R[right] - R[left];
```
2. 如果当前的 $S=mini$，此时 $S$ 已经取到最小值，新的 $(left,right)$ 所对应的 $M_{goal},R_{goal}$ 可以考虑。其**可能更优**，所以用 $\min$ 函数或比较大小求出更小值（即更优值）。
```cpp
Mgoal = min(M[right]-M[left], Mgoal);
Rgoal = min(R[right]-R[left], Rgoal);
```
或写成：
```cpp
if(M[right]-M[left] < Mgoal){
Mgoal = M[right] - M[left];
Rgoal = R[right] - R[left];
}
```
## 特判
最后不要忘记~~有趣的~~ $\#1$ 测试点呀！
通过使用 DeepSeek，豆包，百度体育等进行搜索，可以找到 [这场欧冠 $1/8$ 决赛附加赛](https://tiyu.baidu.com/al/live/detail?matchId=5qyn5rSy5Yag5Yab6IGU6LWbIzIwMjUtMDItMTIj5pu85b275pav54m55Z%2BOdnPnmoflrrbpqazlvrfph4w%3D&tab)（其实题目里也有）。
进入这个网址后，可以发现**打进 $2$ 球未能获胜的球员就是**——[**哈兰德**](https://baike.baidu.com/item/%E5%9F%83%E5%B0%94%E6%9E%97%C2%B7%E5%93%88%E5%85%B0%E5%BE%B7/23507447)！
哈兰德，$2000.7.21$ 出生于英国，是一名挪威足球运动员，现在（$2025.7.31$）效力于曼彻斯特城足球俱乐部。
他的**全名**是：**Erling Braut Haaland**。
注：```Erling Haaland``` 是错误答案，因为题目要求写出**全名**。
注意：虽然测试点 $\#2\sim20$ 的第一行字符串都不含空格，但是测试点 $\#1$ 的第一行是 ```Who is H?```，存在空格，所以要注意读入处理。有以下两种写法。
```cpp
string s; getline(cin, s); //读入整行
if(s == "Who is H?"){
cout << "Erling Braut Haaland";
return 0;
}
```
```cpp
string s; cin >> s; // 读到空格就停止
// 此时 s = "Who"
if(s == "Who"){
cout << "Erling Braut Haaland";
return 0;
}
```
## AC 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
const int MAX_N = 1e6+5;
int M[MAX_N], R[MAX_N], A[MAX_N];
int main(){
string s; getline(cin, s);
// 特判1
if(s == "Who is H?"){
cout << "Erling Braut Haaland";
return 0;
}
int n = s.size();
int k; cin >> k;
// 进球前缀和
for(int i=0; i<n; i++)
M[i+1] = M[i] + (s[i] == 'M'),
R[i+1] = R[i] + (s[i] == 'R');
// 特判2
if(k == 0){
cout << M[n] << ':' << R[n];
return 0;
}
// 净胜球前缀和
for(int i=1; i<=n; i++)
A[i] = M[i] - R[i];
deque <int> q;
int mini = INT_MAX,
Mgoal = 0, Rgoal = 0,
left, right;
for(int i=1; i<=n; i++){
// 单调队列操作
// 1.出队·移除出界元素
if(!q.empty() && q.front() < i-k)
q.pop_front();
// 2.出队·维护单调递减
while(!q.empty() && A[i] >= A[q.back()])
q.pop_back();
// 3.入队·新元素加入
q.push_back(i);
// 避免空队列
if(q.empty()) continue;
int l = q.front(), r = i; // 扣除区间[l+1,r] (求和)
// 净胜球前缀和区间
int dif = A[r] - A[l],
mg = M[r] - M[l], rg = R[r] - R[l];
// 更新答案
if(dif < mini) // 区间内曼城净胜球更少, 扣除
mini = dif,
Mgoal = mg, Rgoal = rg,
left = l, right = r;
else if(dif == mini)
Mgoal = min(mg, Mgoal),
Rgoal = min(rg, Rgoal),
left = l, right = r;
// 净胜球相同情况下, 扣除的进球越少越好(进球多)
}
int Msum = 0, Rsum = 0;
// 如果扣除的曼城净胜球是负数
if(mini < 0)
Msum = Mgoal,
Rsum = Rgoal;
// 扣除
int Mans = M[n] - Msum,
Rans = R[n] - Rsum;
cout << Mans << ':' << Rans;
}
```
## 彩蛋
这道题还有另外一种解法，稍做介绍。
其实这种方法与上文中的正解类似。
在新解法中，我们从皇马净胜球角度出发，转化题意：
通过前缀和、单调队列，求出长度不超过 $K$ 的区间内**皇马的净胜球之和的最大值，并将这个区间扣除**。同理，此时剩余的部分皇马净胜球最小，也即**曼城净胜球最大**。再最大化进球数。
注：如果所有区间中皇马净胜球之和的最大值是**负数**，就说明**所有区间内曼城都占优**，不需要扣除任何区间。
$b=\{r_1-m_1,r_2-m_2,\dots,r_N-m_N\}$，
改为求 $S'=\sum_{i=left}^{right}b_i$ 的**最大值**，以及此时以下两个式子的最大值。
$$
\sum_{i=1}^{N}m_i-\sum_{i=left}^{right}m_i
$$
$$
\sum_{i=1}^{N}r_i-\sum_{i=left}^{right}r_i
$$
如果 $S'<0$，直接求 $\sum_{i=1}^{N}m_i$ 和 $\sum_{i=1}^{N}r_i$ 的值。
### 代码调整
代码主要需要更改的部分如下：
1. 更改 $A$ 数组的值（与原值刚好相反）；
2. 维护双端队列**单调递减**而非单调递增；
3. 记录每次 $S'$ 的**最大值**而非最小值；
4. $S'<0$ 时特殊处理。
### 新代码
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
int M[N], R[N], a[N];
int main(){
string s; getline(cin, s);
// 特判1
if(s == "Who is H?"){
cout << "Erling Braut Haaland";
return 0;
}
int n = s.size();
int k; cin >> k;
// 进球前缀和
for(int i=0; i<n; i++)
M[i+1] = M[i] + (s[i] == 'M'),
R[i+1] = R[i] + (s[i] == 'R');
// 特判2
if(k == 0){
cout << M[n] << ':' << R[n];
return 0;
}
// 净胜球前缀和
for(int i=1; i<=n; i++)
a[i] = R[i] - M[i];
// 改成计算皇马净胜球
deque <int> q;
int maxi = INT_MIN,
Mgoal = 0, Rgoal = 0,
left, right;
for(int i=1; i<=n; i++){
// 单调队列操作
// 1.出队·移除出界元素
if(!q.empty() && q.front()<i-k)
q.pop_front();
// 2.出队·维护单调递增
while(!q.empty() && a[i] <= a[q.back()])
q.pop_back();
// 3.入队·新元素加入
q.push_back(i);
// 避免空队列
if(q.empty()) continue;
int l = q.front(), r = i; // 扣除区间[l+1,r] (求和)
// 净胜球前缀和区间
int dif = a[r] - a[l],
mg = M[r] - M[l], rg = R[r] - R[l];
// 更新答案
if(dif > maxi) // 区间内皇马净胜球增加, 扣除
maxi = dif,
Mgoal = mg, Rgoal = rg,
left = l, right = r;
else if(dif == maxi)
Mgoal = min(mg, Mgoal),
Rgoal = min(rg, Rgoal),
left = l, right = r;
// 净胜球相同情况下, 扣除的进球越少越好(进球多)
}
int Msum = 0, Rsum = 0;
// 如果扣除皇马净胜球是正数
if(maxi > 0)
Msum = Mgoal,
Rsum = Rgoal;
// 扣除
int Mans = M[n] - Msum,
Rans = R[n] - Rsum;
cout << Mans << ':' << Rans;
}
```
## 声明
本篇题解同时也是 [T606108 欧冠附加赛-XRX](https://www.luogu.com.cn/problem/T606108) 的题解，但 T606108 数据未更正。
需要将以上 AC 代码的第 $3$ 行：
```cpp
const int MAX_N = 1e6+5;
```
调整为如下代码即可 AC。
```cpp
const int MAX_N = 1.1e6+5
```
## 结尾
完结撒花！
作者：[Doraeman](https://www.luogu.com.cn/user/1511943)。
完成时间：$2025.8.1$。