TopCoder SRM603: SplitIntoPairs
\(X < 0\) であるのがポイント。
Aを負の数のグループと、非負の数のグループに分ける。
同じグループ同士でペアを作ると積は必ず 0 以上になり、それぞれのグループは高々1つだけあまる。
もし両方のグループで1つずつ余った場合は、それらでペアを組むようにすればよい。
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; } }