Codeforces 998 算法竞赛题解：从构造到贪心的多题解析
A. 数组三元组匹配问题
题目给出四个整数，要求判断通过特定组合方式最多能形成多少组相等的三元组。具体而言，给定 a₁, a₂, a₄, a₅，构造三个值：
- c₁ = a₁ + a₂
- c₂ = a₄ − a₂
- c₃ = a₅ − a₄
将这三个结果排序后，统计其中相同元素的最大数量。若三者相等，输出 3；若有两者相等，输出 2；否则输出 1。
实现时只需计算三个表达式，排序后比较即可。
#include <bits/stdc++.h>
using namespace std;
void solve() {
int a1, a2, a4, a5;
cin >> a1 >> a2 >> a4 >> a5;
vector<int> vals = {a1 + a2, a4 - a2, a5 - a4};
sort(vals.begin(), vals.end());
if (vals[0] == vals[2]) cout << 3;
else if (vals[0] == vals[1] || vals[1] == vals[2]) cout << 2;
else cout << 1;
cout << '\n';
}
int main() {
int t; cin >> t;
while (t--) solve();
return 0;
}
B. 多序列顺序一致性验证
给定 n 个长度为 m 的序列，需判断是否存在一种排列，使得所有序列在重新索引后呈现递增顺序。核心思路是以第一个元素为基准建立映射关系。
步骤如下：
- 对每个序列内部排序。
- 提取每个序列的最小值（即首个元素），检查其是否小于 n，防止索引越界。
- 用数组
p记录：第 i 小的首元素对应原序列编号。 - 随后逐列验证后续元素是否严格按全局递增顺序分布。
若任意位置不符合预期，则无解，返回 -1；否则输出合法排列。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2005;
int grid[MAXN][MAXN], pos[MAXN];
void solve() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j)
cin >> grid[i][j];
sort(grid[i] + 1, grid[i] + m + 1);
}
for (int i = 1; i <= n; ++i) {
if (grid[i][1] >= n) {
cout << "-1\n";
return;
}
pos[grid[i][1] + 1] = i;
}
int expected = n;
for (int col = 2; col <= m; ++col) {
for (int rank = 1; rank <= n; ++rank) {
int seq_id = pos[rank];
if (grid[seq_id][col] != expected++) {
cout << "-1\n";
return;
}
}
}
for (int i = 1; i <= n; ++i)
cout << pos[i] << " ";
cout << "\n";
}
int main() {
int t; cin >> t;
while (t--) solve();
return 0;
}
C. 数对和等于 k 的最大匹配数
给定 n 个整数和目标值 k，求最多可组成多少对数字 (a, b)，满足 a + b = k。注意每数只能使用一次。
策略：
- 使用哈希表记录各数值出现频次。
- 枚举去重后的升序数组 d，对每个 d[i]，查找补数 c = k − d[i]。
- 若 d[i] < c，累加 min(频次[d[i]], 频次[c])。
- 若 d[i] == c，可自配对，贡献为 freq / 2。
- 当 d[i] > c 时终止循环，避免重复计数。
#include <bits/stdc++.h>
using namespace std;
map<int, int> freq;
vector<int> unique_nums;
int arr[200005];
void solve() {
int n, k;
cin >> n >> k;
freq.clear();
for (int i = 1; i <= n; ++i) {
cin >> arr[i];
freq[arr[i]]++;
}
unique_nums.assign(freq.begin(), freq.end());
sort(unique_nums.begin(), unique_nums.end());
int pairs = 0;
for (auto [val, cnt] : unique_nums) {
int complement = k - val;
if (val > complement) break;
if (val == complement) {
pairs += cnt / 2;
} else if (freq.count(complement)) {
pairs += min(cnt, freq[complement]);
}
}
cout << pairs << '\n';
}
int main() {
int t; cin >> t;
while (t--) solve();
return 0;
}
D. 数组非递减性操作判定
给定一个正整数数组，允许对相邻两数执行操作：同时减去它们的最小值。问是否可通过若干操作使数组变为非递减序列。
关键观察：
- 操作本质是将较小数归零，并从较大数中扣除该值。
- 一旦某位置变为 0，其与邻接元素的操作不再改变对方。
- 最优策略是从左至右依次处理每对相邻元素。
模拟过程：遍历数组，对每对 (a[i−1], a[i]) 减去 min(a[i−1], a[i])。最终检查结果是否为非递减序列。
#include <bits/stdc++.h>
using namespace std;
int a[200005];
void solve() {
int n; cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
for (int i = 2; i <= n; ++i) {
int sub = min(a[i-1], a[i]);
a[i-1] -= sub;
a[i] -= sub;
}
for (int i = 1; i < n; ++i) {
if (a[i] > a[i+1]) {
cout << "NO\n";
return;
}
}
cout << "YES\n";
}
int main() {
int t; cin >> t;
while (t--) solve();
return 0;
}
