SRM603 div2 Med SplitIntoPairs

TopCoder Statistics - Match Overview

問題概要

  • 素数が偶数の配列Aが与えられる
  • Aの要素2つを選んでペアを|A|/2個作る
  • ペアの積がX以上となるようなペアの最大数を求めよ

制約

  • |A| % 2 = 0
  • -109≦A≦109
  • -109≦X≦-1

解説

Xが負であることがポイント。

偶数偶数と奇数奇数ペアは絶対に正になる。

できるだけ同じ符号同士でペアにすればいい。

符号が正である要素が偶数個あるなら全てのペアを同じ符号同士にできる(答えは|A|/2個)。

符号が正である要素が奇数個なら偶数*奇数のペアが1つできてしまう。

偶数の要素と奇数の要素の全ての組み合わせの積を計算して最大値がX以上であれば答えは|A|/2、そうでないなら|A|/2-1。

コード

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;
class SplitIntoPairs {
public:
  int makepairs(vector <int> A, int X) {
    int plus = 0;
    FOR(i,0,A.size()) {
      if(A[i] >= 0) plus++;
    }
    if(plus % 2 == 0) return A.size() / 2;
    else {
      ll mx = -2e9;
      sort(A.begin(), A.end());
      for(int i = A.size() - 1; A[i] >= 0; i--) {
        for(int j = 0; A[j] < 0; j++) {
          mx = max(mx, (ll)A[i]*(ll)A[j]);
        }
      }
      if(mx >= X) return A.size() / 2;
      else return A.size() / 2 - 1;
    }
  }
};