SRM 603 Div2 Medium SplitIntoPairs

問題

SRM 603 - TopCoder Wiki

偶数の整数リストから2組ずつのペアを作る. その時ペアの席が与えられたXよりも大きくなる数を数えた時,最大のペア数を答えよという問題

解答

  • Xは負の数だというのが大きなポイント
  • 負の数同士,正の数同士をペアリングすればXより大きいことは確実となる.
  • あとは負の数同士,正の数同士をペアにしなければいけない状況の時,成り立つかどうかをチェックする
  • その場合負の数の最大値,正の数の最小値を選ぶのが,最も大きな値となる

コードはかなり冗長.

class SplitIntoPairs
{
public:
  int makepairs(vector <int> A, int X)
    {
      vector<int> negative;
      vector<int> positive;
      int n = A.size();
      int res = 0;
      for(int i = 0; i < n; i++) {
        if (A[i] <= 0) negative.push_back(A[i]);
        else positive.push_back(A[i]);
      }
      sort(negative.begin(), negative.end());
      sort(positive.begin(), positive.end());
      for(int i = 1; i < negative.size(); i+=2) {
        if ((double)negative[i] * negative[i-1] >= X) res++;
      }
      for(int i = positive.size()-2; i >= 0; i -= 2) {
        if ((double)positive[i] * positive[i+1] >= X) res++;
      }
      if (negative.size() % 2 == 1 && positive.size() % 2 == 1){
        if ((double)positive[0] * negative[negative.size()-1] >= X) res++;
      }
      return res;
    }
};