Задача №1 (заимствовано из каких-то учебных заданий):Olej писал(а): Вариант жадных алгоритмов
Вариант решения:В колонии на осваиваемой планете решили выбрать органы управления. Каждый из его жителей организовал партию, которую сам и возглавил. Отметим, что, ко всеобщему удивлению, даже в самой малочисленной партии оказалось не менее двух человек. К сожалению, финансовые трудности не позволили создать парламент, куда вошли бы, как предполагалось по правилам, президенты всех партий. Посовещавшись, колонисты решили, что будет достаточно, если в парламенте будет хотя бы один член каждой партии. Помогите организовать такой, как можно более малочисленный, парламент, в котором будут представлены члены всех партий.
Каждая партия и, соответственно, её президент имеют одинаковый порядковый номер от 1 до N (4 ⩽ N ⩽ 150). Вам даны списки всех N партий планеты.
Выведите предлагаемый вами парламент в виде списка номеров его членов.
- каждая партия представлена строкой номеров (вектор)
- ищем номер, который наиболее часто встречается во всех строках - включаем этот номер в результат
- очищаем все строки (вектора), куда входил выбранный номер
- повторяем с п.1 последовательно до тех пор, пока все строки станут пустыми
Код: Выделить всё
#include <bits/stdc++.h>
using namespace std;
ostream& operator <<( ostream& out, const vector<int>& obj ) {
out << "[ ";
for( auto i: obj ) cout << i << " ";
return out << "]";
}
ostream& operator <<( ostream& out, const vector< vector<int> >& obj ) {
for( auto &x: obj )
out << x << endl;
return out;
}
int main( int argc, char *argv[] ) {
bool debug = argc > 1;
vector< vector<int> > parts;
int n = 0;
while( true ) {
string e;
getline( cin, e );
if( !cin || 0 == e.length() ) break;
istringstream ist( e );
int d;
vector<int> line;
while( ist >> d )
line.push_back( d );
if( find( line.begin(), line.end(), n + 1 ) == line.end() )
line.push_back( n + 1 );
parts.push_back( line );
n++;
}
vector<int> rezs( 0 );
cout << parts;
while( true ) {
if( debug )
cout << "-------------------------------" << endl << parts;
vector<int> memb( parts.size() + 1, 0 );
for( auto &x: parts )
for( auto i: x )
memb[ i ]++; // частоты строк
auto mx = max_element( memb.begin(), memb.end() );
if( 0 == *mx ) break;
n = mx - memb.begin(); // самый частый номер
rezs.push_back( n );
if( debug ) cout << memb << " => " << *mx << " | " << n << endl;
for( auto x = parts.begin(); x < parts.end(); x++ )
if( find( x->begin(), x->end(), n ) != x->end() )
x->clear(); // очистить строки содержащие этот номер
}
cout << "результат: " << rezs << endl;
}
Код: Выделить всё
[olej@dell part]$ ./part < p1.in
[ 1 2 ]
[ 2 4 6 7 ]
[ 3 6 7 ]
[ 4 5 7 ]
[ 5 6 ]
[ 6 4 ]
[ 7 5 ]
результат: [ 6 5 1 ]
[olej@dell part]$ ./part < p2.in
[ 2 4 7 1 ]
[ 4 6 7 5 2 ]
[ 3 6 7 ]
[ 4 5 7 1 ]
[ 5 6 2 3 ]
[ 6 4 7 1 ]
[ 7 5 2 ]
результат: [ 7 2 ]