Official
C - Socks Editorial by yuto1115
解説色ごとに靴下をグループ分けして考えます。ある色の靴下が \(C\) 枚あるとき、この色の靴下同士をペアにする操作を繰り返すことで、\(\lfloor \frac{C}{2} \rfloor\) 回の操作が可能です。よって、std::map などの連想配列を用いて「何色の靴下が何枚あるか」という情報を管理すればよいです。
実装例 (C++) :
#include<bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
map<int, int> mp;
for (int i = 0; i < n; i++) {
int a;
cin >> a;
++mp[a];
}
int ans = 0;
for (auto [_, cnt]: mp) ans += cnt / 2;
cout << ans << endl;
}
posted:
last update: