TopCoder SRM603: SplitIntoPairs

\(X < 0\) であるのがポイント。

Aを負の数のグループと、非負の数のグループに分ける。
同じグループ同士でペアを作ると積は必ず 0 以上になり、それぞれのグループは高々１つだけあまる。
もし両方のグループで１つずつ余った場合は、それらでペアを組むようにすればよい。

public class SplitIntoPairs {
    public int makepairs(int[] A, int X) {
        int n = A.Length;
        int ans = 0;
        var g1 = A.Where(a => a >= 0).ToArray();
        var g2 = A.Where(a => a < 0).ToArray();
        ans = g1.Length / 2 + g2.Length / 2;
        if (g1.Length % 2 != 0 && g2.Length % 2 != 0) {
            if (1L * g1.Min() * g2.Max() >= X)
                ans++;
        }
        return ans;
    }
}