読者です 読者をやめる 読者になる 読者になる

SRM500 Div2 SRMCards

問題
与えられたこのなる数字の書かれたカードの中から一枚ずつ選んで取り除くゲームをする。
取り除く際に、もし選んだカードの数字と前後の数字を持つカードが存在すれば、それぞれも抜き取らなければならない。

カードを選べる回数を最大化せよ。

解法
ソートして小さい順に取り除くだけ。見ている数より1つ大きい数字が合った場合、ループのカウントを1つ増やしてスキップ処理をする。

class SRMCards {
public:
  int maxTurns(vector <int> cards) {
    sort(ALL(cards));
    int const N = cards.size();
    vector<bool> used(N);
    int cnt = 0;
    for(int i=0; i<N; i++) {
      if(i+1<N && cards[i]+1 == cards[i+1]) i++;
      cnt++;
    }
    
    return cnt;
  }
};