23 December

[PR]

[PR]上記の広告は3ヶ月以上新規記事投稿のないブログに表示されています。新しい記事を書く事で広告が消えます。

09 January

SRM603 div2 medium

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12939

要素数がNの配列Aがある。その中からN/2個のペアを作る。
そのペアの中で積がX以上になる個数を求めよ。
なお、Xは負の数であることが保証されている。

解法

最初、A中に負の数の個数が何個あるか求めてから
個数が奇数か偶数かとかで場合分けしようとしたが、
ソートしてから、前から二個ずつペアにしていき、
その積がXを超えている個数をカウントしていけば解けることに途中で気づいた。
the productの意味を積だと知らず、少し手間取った。
英語は大事。


#include<iostream>
#include<vector>
#include<map>
#include<functional>
#include<algorithm>
#include<string>
#include<climits>

using namespace std;

class SplitIntoPairs{
public:
	int makepairs(vector<int> A,int X){
		sort(A.begin(),A.end());
		int cnt=0;
		for(int i=0;i<A.size()-1;i+=2)
			if((long long)A[i]*A[i+1] >= X)cnt++;
		return cnt;
	}
};