当前博客仍在持续更新完善中，敬请期待～
双指针
题单 🧑🏻💻
| 题目来源 | 题目名称 | 题目链接 | 备注 | 难度 |
|---|---|---|---|---|
| Codeforces 1399C | Boats Competition | 链接🔗 | 思维 + 双指针 | 🟡 |
题解 🚀
Boats Competition
题目信息 📚
【题目名称】Codeforces 1399C - Boats Competition
【题目描述】
There are $n$ people who want to participate in a boat competition. The weight of the $i$-th participant is $w_i$. Only teams consisting of two people can participate in this competition. As an organizer, you think that it’s fair to allow only teams with the same total weight.
So, if there are $k$ teams $(a_1,b_1), (a_2,b_2), \ldots, (a_k,b_k)$, where $a_i$ is the weight of the first participant of the $i$-th team and $b_i$ is the weight of the second participant of the $i$-th team, then the condition $a_1+b_1 = a_2+b_2 = \cdots = a_k+b_k = s$, where $s$ is the total weight of each team, should be satisfied.
Your task is to choose such $s$ that the number of teams people can create is the maximum possible. Note that each participant can be in no more than one team.
You have to answer $t$ independent test cases.
【输入】
The first line of the input contains one integer $t$ $(1 \leq t \leq 1000)$ — the number of test cases. Then $t$ test cases follow.
The first line of each test case contains one integer $n$ $(1 \leq n \leq 50)$ — the number of participants. The second line of the test case contains $n$ integers $w_1, w_2, \ldots, w_n$ $(1 \leq w_i \leq n)$, where $w_i$ is the weight of the $i$-th participant.
【输出】
For each test case, print one integer $k$: the maximum number of teams people can compose with the total weight $s$, if you choose $s$ optimally.
【输入样例】
5
5
1 2 3 4 5
8
6 6 6 6 6 6 8 8
8
1 2 2 1 2 1 1 2
3
1 3 3
6
1 1 3 4 2 2【输出样例】
2
3
4
1
2【提示】
In the first test case of the example, we can reach the optimal answer for $s=6$. Then the first boat is used by participants 1 and 5, and the second boat is used by participants 2 and 4 (indices are the same as weights).
In the second test case of the example, we can reach the optimal answer for $s=12$. Then the first 6 participants can form 3 pairs.
In the third test case of the example, we can reach the optimal answer for $s=3$. The answer is 4 because we have 4 participants with weight 1 and 4 participants with weight 2.
In the fourth test case of the example, we can reach the optimal answer for $s=4$ or $s=6$.
In the fifth test case of the example, we can reach the optimal answer for $s=3$. Note that the participant with weight 3 can’t use the boat because there is no suitable pair for him in the list.
【原题链接】
https://codeforces.com/problemset/problem/1399/C
题目解析 🍉
【题目分析】
题目的数据范围非常小，因此可以采用「枚举」总重量 s 的方式，判断每一个合法的 s 能够组成多少队伍，取答案最大值即可。
判断过程可以使用 map 桶思想计数，也可以采用「贪心 + 双指针」算法。
【C++ 代码】枚举 + 贪心 + 双指针 ✅
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 110;
int n, w[N];
// 枚举 + 双指针
void solve_2() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> w[i];
sort(w + 1, w + n + 1);
// 枚举可能的权重之和s（最少为1+1=2，最大为n+n=2n，因为w<=n）
// 枚举s后，问题被简化成：对于数组w，有多少队伍的和为s
int maxteams = 0;
for (int s = 2; s <= 2 * n; s++) {
int teams = 0; // 对于当前权重和s，能满足的队伍数存入teams中
// 权重数组排序经过排序后为升序，故可以使用双指针，统计共有多少对权重和为s
int i = 1, j = n;
while (i < j) {
if (w[i] + w[j] == s) {
i++, j--, teams++;
} else if (w[i] + w[j] < s) {
i++;
} else {
j--;
}
}
maxteams = max(maxteams, teams);
}
cout << maxteams << endl;
}
int main() {
ios::sync_with_stdio(false); //cin读入优化
cin.tie(0);
int T;
cin >> T;
while (T--) {
solve_2();
}
return 0;
}【C++ 代码】枚举 + map ✅
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 110;
int n, w[N];
// 枚举 + 统计
void solve_1() {
cin >> n;
unordered_map<int, int> mp;
// 输入权重数组w，并统计每个权重出现的次数
for (int i = 1; i <= n; i++) {
cin >> w[i];
mp[w[i]]++;
}
// 枚举可能的权重之和s（最少为1+1=2，最大为n+n=2n，因为w<=n）
// 枚举s后，问题被简化成：对于数组w，有多少队伍的和为s
int maxteams = 0;
for (int s = 2; s <= 2 * n; s++) {
int teams = 0; // 对于当前权重和s，能满足的队伍数存入teams中
// 对权重i枚举，看i和s-i是否均出现在w中
for (int i = 1; i <= s / 2; i++) {
if (mp[i] && mp[s - i]) {
if (i == s - i)
teams += mp[i] / 2;
else
teams += min(mp[i], mp[s - i]);
}
}
if (teams > maxteams) maxteams = teams;
}
cout << maxteams << endl;
}
int main() {
ios::sync_with_stdio(false); //cin读入优化
cin.tie(0);
int T;
cin >> T;
while (T--) {
solve_1();
}
return 0;
}
