C - Boats Competition

cpcodeforcesdiv3greedyexhaustive search

最終更新日

Table of Contents

Loading...

問題

https://codeforces.com/contest/1399/problem/C (新しいタブで開く)

問題文

nn 人の人がいて、それぞれの体重は wiw_i

ある ss に対して、 ai+aj=sa_i + a_j = s となるようにペアを作る。
ただし、 iji \ne j で、 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

考察

1win1 \le w_i \le n という制約に加えて、 nn が小さいことから、全探索してシミュレーションしても間に合う。
具体的には、 ss11 から 2n2 n まで全探索したときに、相異なる i,ji, j に対して ai+aj=sa_i + a_j = s となるペアがいくつ作れるかを数えればいい。

コード

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