問題
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; }