yukicoder No.29 パワーアップ 解説

問題文

解説

まずこの問題で気づくべきことは
4個パワーアップに同じものを4個使うよりも、2個パワーアップに同じものを二つ使った方がいい
ということである。
まず、以下の配列を用いる。
$item_i$=$i$個目のアイテムが何個あるか
毎回ループを回すごとに$item_{A_i}$,$item_{B_i}$,$item_{C_i}$を一増やす。
あとは、2個パワーアップの回数を数え、それに4個パワーアップができる回数を足す。

解答例

#include <bits/stdc++.h>
using namespace std;

int main(){
  int n,ans=0;cin>>n;
  vector<int> item(11,0);
  for(int i=0;i<n;i++){
    int a_i,b_i,c_i;cin>>a_i>>b_i>>c_i;
    item[a_i]++;
    item[b_i]++;
    item[c_i]++;
  }
  for(int i=1;i<=10;i++){
    ans+=item[i]/2;
    item[i]%=2;
  }
  int sum=0;
  for(int i=1;i<=10;i++)sum+=item[i];
  cout<<ans+sum/4<<endl;
}