A. 全长度减法 题解

---

一、题意理解

给定一个长度为 $n$ 的排列 $p$。对每个 $k = 1, 2, \dots, n$（按顺序），必须恰好选择一个长度为 $k$ 的子数组，将其中所有元素减 $1$。目标是使最终所有元素变为 $0$。判断是否可行。

---

二、关键观察

2.1 最大值 $n$ 的要求

元素 $n$ 需要被减 $n$ 次才能变为 $0$。由于总共只有 $n$ 次操作，这意味着每次操作都必须包含元素 $n$。

因此，所有子数组的公共交集必须包含 $n$ 的位置。

2.2 次大值 $n-1$ 的要求

元素 $n-1$ 需要被减 $n-1$ 次。它最多被排除在一次操作之外（因为总共有 $n$ 次操作，它必须参与其中 $n-1$ 次）。

• 长度为 $1$ 的子数组只会包含 $n$（由上一步可知），因此可以排除 $n-1$。
• 长度为 $2$ 的子数组必须同时包含 $n$ 和 $n-1$，否则 $n-1$ 将少参与一次操作。

因此，$n-1$ 必须与 $n$ 相邻。

2.3 一般规律

对于任意值 $i$（从 $n$ 向下考虑），它需要被减 $i$ 次，因此最多被排除在 $n - i$ 次操作之外。

• 长度为 $1, 2, \dots, n-i$ 的子数组可以排除 $i$。
• 长度为 $n-i+1$ 的子数组必须包含 $i$。

这意味着所有值 $\{i, i+1, \dots, n\}$ 必须包含在长度为 $n-i+1$ 的子数组中，因此它们在原排列中的位置必须构成一个连续段。

2.4 等价条件

排列 $p$ 可行，当且仅当满足以下条件：

对于每个 $i$ 从 $1$ 到 $n$，值 $\{i, i+1, \dots, n\}$ 的位置构成一个连续段。

等价地，排列必须是单峰的（mountain）：先递增后递减。

也就是说，从排列的两端交替取最小值，可以依次取出 $1, 2, \dots, n$。

---

三、算法流程

我们可以模拟以下过程：

1. 设置左指针 $l = 0$，右指针 $r = n-1$。
2. 对于 $i = 1, 2, \dots, n$：
   • 如果 $p[l] = i$，说明 $i$ 在左端，将 $l$ 右移一位。
   • 否则，如果 $p[r] = i$，说明 $i$ 在右端，将 $r$ 左移一位。
   • 否则，排列不是单峰的，输出 NO 并返回。
3. 如果循环顺利完成，输出 YES。

---

四、正确性证明

• 充分性：如果排列满足上述条件，我们可以按以下方式构造操作：

  • 对于 $k = n$，选择整个数组减 $1$。
  • 对于 $k = n-1$，选择除去已归零的那一端元素后的子数组。
  • 依此类推，每次从两端逐步收缩子数组。

• 必要性：已在上文通过分析每个值需要参与的操作次数证明。

---

五、标程解析

void solve() {
  int n;
  std::cin >> n;
  std::vector<int> p(n);
  for (int i = 0; i < n; i++) {
    std::cin >> p[i];
  }  
 
  int l = 0, r = n - 1;
  for (int i = 1; i <= n; i++) {
    if (p[l] == i) {
      l++;
    } else if (p[r] == i) {
      r--;
    } else {
      NO;
      return;
    }
  }
  YES;
}

步骤：

1. 读入排列 $p$。
2. 初始化左右指针 $l = 0$，$r = n-1$。
3. 从小到大枚举 $i = 1$ 到 $n$：
   • 如果当前左端是 $i$，则"移除"左端（l++）。
   • 如果当前右端是 $i$，则"移除"右端（r--）。
   • 如果都不是，说明排列不满足条件，输出 NO。
4. 全部成功移除则输出 YES。

时间复杂度 $O(n)$，总复杂度 $O(t \cdot n)$。

---

六、样例验证

样例 1

4
1 3 4 2

• $i=1$：$p[l]=1$ → $l=1$
• $i=2$：$p[r]=2$ → $r=2$
• $i=3$：$p[l]=3$ → $l=2$
• $i=4$：$p[l]=4$ → 完成 → YES ✅

样例 2

5
1 5 2 4 3

• $i=1$：$p[l]=1$ → $l=1$
• $i=2$：$p[l]=5 \neq 2$，$p[r]=3 \neq 2$ → NO ✅

样例 3

5
2 4 5 3 1

• $i=1$：$p[r]=1$ → $r=3$
• $i=2$：$p[l]=2$ → $l=1$
• $i=3$：$p[r]=3$ → $r=2$
• $i=4$：$p[l]=4$ → $l=2$
• $i=5$：$p[l]=5$ → 完成 → YES ✅

样例 4

3
3 1 2

• $i=1$：$p[l]=3 \neq 1$，$p[r]=2 \neq 1$ → NO ✅

---

七、代码实现（C++）

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int> p(n);
    for (int i = 0; i < n; i++) {
        cin >> p[i];
    }
    
    int l = 0, r = n - 1;
    for (int i = 1; i <= n; i++) {
        if (p[l] == i) {
            l++;
        } else if (p[r] == i) {
            r--;
        } else {
            cout << "NO\n";
            return;
        }
    }
    cout << "YES\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

---

八、复杂度分析

• 每个测试用例仅需 $O(n)$ 时间扫描排列一次。
• $n \leq 100$，$t \leq 100$，总复杂度极小。
• 空间复杂度 $O(n)$。