問題
https://codeforces.com/contest/1399/problem/C (新しいタブで開く)
問題文
人の人がいて、それぞれの体重は 。
ある に対して、 となるようにペアを作る。
ただし、 で、 1 人の人は 1 つのペアにしか入れない。
最大で何ペア作れる?
制約
サンプル
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
考察
という制約に加えて、 が小さいことから、全探索してシミュレーションしても間に合う。
具体的には、 を から まで全探索したときに、相異なる に対して となるペアがいくつ作れるかを数えればいい。
コード
https://codeforces.com/contest/1399/submission/126144846 (新しいタブで開く)
void solve() {
int n;
cin >> n;
vector<int> w(n);
rep(i, n) cin >> w[i];
int ans = 0;
rep(s, 2 * n) {
int tmpa = 0;
set<int> used;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (s + 1 == w[i] + w[j] && !used.count(i) && !used.count(j)) {
tmpa++;
used.insert(i);
used.insert(j);
}
}
}
ans = max(ans, tmpa);
}
cout << ans << endl;
}