题解 CF1399C 【Boats Competition】
Suuon_Kanderu
2020-08-20 13:05:11
看到此题数据范围不大，我们想到暴力枚举 $s$，最后取最大值。
我们需要找到 $a_i + a_j = s$ 的数量，容易想到 two pointer 解法，但我们也可以是用更为简单的方法：
移项，得到 $s - a_i = a_j$ 。首先我们把每个数在桶 cnt 里记录。$cnt(i)$ 就表示 i 在整个序列中出现过几次。
之后统计 $a_i + a_j = s$ 的数量，从前往后扫。对于每个 i ，我们需要判断 $cnt(a(i))$ 是否至少为 1，因为可能在之前 $a(i)$ 已经用过了，肯定不符合条件。
满足 $cnt(a(i)) >0$ 后，有两种情况是满足条件的：
$$s-a(i) \not= a(i) ,cnt(s-a(i))>0 $$
$$s-a(i) = a(i),cnt(a(i))>1 $$
判断即可，满足条件后我们把 $cnt(a(i)) \gets cnt(a(i))-1,cnt(s-a(i)) \gets cnt(s-a(i))-1$,表示这两个数已经被选了。
需要注意！我们每次枚举后都需要将 cnt 数组还原。
此代码时间复杂度是 $O(Tn^2)$ 的。
```
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
typedef long long ll;
int n , a[200] ;
int check(int cnt[] , int t) {
int now = 0;
for(int j = 1; j <= n; j++) {
if(t - a[j] < 0)continue;
if(cnt[a[j]] && ((cnt[t - a[j]] && t - a[j] != a[j]) //情况一
|| (t - a[j] == a[j] && cnt[a[j]] >= 2)) ) {//情况2
now++;//记录答案
cnt[t - a[j]]--;
cnt[a[j]]--;
}
}
return now;
}
int main() {
int t;scanf("%d" , &t);
while(t--) {
int cnt[200] , ans = 0;//答案
memset(cnt , 0 , sizeof(cnt));
scanf("%d" , &n);
for(int i = 1; i <= n; i++) {
scanf("%d" , &a[i]);
cnt[a[i]]++;
}int t[200];//将 cnt 数组还原
memcpy(t , cnt , sizeof(t));
for(int i = 1; i <= 2*n; i++) {
ans = max(ans , check(cnt , i));
memcpy(cnt , t , sizeof(cnt));
}
printf("%d\n" , ans);
}
}
```