プログラミング問題#6:priority queue練習問題(C++プログラム設計9週目)
5308 ワード
説明
正の整数aが正の整数bよりも優先されるという意味を定義する.
*aの素因数の数(自身を含まない)はbの素因数の数より多い.
*両者の素因数が等しい場合、数値が大きい方が優先度が高い.
最初の要素数が0のコンテナが与えられ、その後、10の要素が追加されます.追加するたびに、最も優先度の高い要素と最も低い要素が出力され、コンテナから削除されます.
入力
1行目:num(要素の追加回数num<=30)
次の10*num行は、行ごとに正の整数n(n<1000000)である.
しゅつりょく
10個の整数を入力するたびに、出力コンテナの中で最も優先度の高い要素と最も低い要素がスペース間隔で表示されます.
サンプル入力
サンプル出力
ヒントソースは他人のもので、その中で関数オブジェクトが使われていて、よく使われています.方法はとても良いソースです
正の整数aが正の整数bよりも優先されるという意味を定義する.
*aの素因数の数(自身を含まない)はbの素因数の数より多い.
*両者の素因数が等しい場合、数値が大きい方が優先度が高い.
最初の要素数が0のコンテナが与えられ、その後、10の要素が追加されます.追加するたびに、最も優先度の高い要素と最も低い要素が出力され、コンテナから削除されます.
入力
1行目:num(要素の追加回数num<=30)
次の10*num行は、行ごとに正の整数n(n<1000000)である.
しゅつりょく
10個の整数を入力するたびに、出力コンテナの中で最も優先度の高い要素と最も低い要素がスペース間隔で表示されます.
サンプル入力
1
10 7 66 4 5 30 91 100 8 9
サンプル出力
66 5
ヒントソースは他人のもので、その中で関数オブジェクトが使われていて、よく使われています.方法はとても良いソースです
#include <iostream>
#include <cmath>
#include <set>
using namespace std;
//
bool isPrime(int iVal)
{
for (int i = 2; i <= sqrt((float)iVal); i++)
{
if (iVal % i == 0)
return false;
}
return true;
}
//
int getFactor(int a)
{
int sum = 0;
int k = 0;
for (int i = 2; i <= sqrt((float)a); i++)
{
if (a % i == 0)// a/i = k,
{
k = a / i;
if (i != k && isPrime(k))
sum += 1;
if (isPrime(i))
{
sum += 1;
}
}
}
return sum;
}
// ,
class Compare_Class_Up
{
public:
bool operator()(const int& a, const int& b)
{
int sumA = 0, sumB = 0;
sumA = getFactor(a);
sumB = getFactor(b);
if (sumA == sumB)
{
if (a < b)
{
return true;
}
else
return false;
}
else if (sumA > sumB)
{
return false;
}
else
return true;
}
};
int main()
{
set<int, Compare_Class_Up> queue;
int n = 0;
cin >> n;
while (n--)
{
int num;
for (int i = 0; i < 10; i++)
{
cin >> num;
queue.insert(num);
}
int min = *(queue.begin());
int max = *(queue.rbegin());
queue.erase(max);
queue.erase(min);
cout << max << ' ' << min << endl;
}
return 0;
}