-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathgrinch.cpp
More file actions
121 lines (101 loc) · 3.05 KB
/
grinch.cpp
File metadata and controls
121 lines (101 loc) · 3.05 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <iostream>
#include <vector>
#include <set>
#include <random>
#include <chrono>
template <typename T>
void print_vector( std::vector<T> &vec )
{
std::cout << "{ ";
for( auto it = vec.begin(); it != vec.end(); ++it )
{
std::cout << *it << ", ";
}
std::cout << "\b\b }" << std::endl;
}
template <typename T>
void print_set( std::multiset<T> &set )
{
std::cout << "{ ";
for( auto it = set.begin(); it != set.end(); ++it )
{
std::cout << *it << ", ";
}
std::cout << "\b\b }" << std::endl;
}
int main()
{
typedef std::chrono::high_resolution_clock myclock;
std::mt19937 generator;
generator.seed( myclock::now().time_since_epoch().count() );
const int max_score = 100;
std::uniform_int_distribution<int> distribution( 1, max_score );
std::vector<int> players;
for( int i = 0; i < 50; ++i )
{
players.push_back( distribution( generator ) );
}
std::cout << "unsorted players:" << std::endl;
print_vector( players );
std::multiset<int> good_team, bad_team;
int operations = 0;
int initial_sort_operations = 0;
for( auto it = players.begin(); it != players.end(); ++it )
{
if( *it > max_score / 2 )
{
good_team.insert( *it );
}
else
{
bad_team.insert( *it );
}
++operations;
++initial_sort_operations;
}
std::cout << "good team before balancing:" << std::endl;
print_set( good_team );
std::cout << "bad team before balancing:" << std::endl;
print_set( bad_team );
int balance_operations = 0;
auto bad_it = bad_team.rbegin();
while( bad_team.size() > good_team.size() )
{
bad_it = bad_team.rbegin();
good_team.insert( *bad_it );
bad_team.erase( *bad_it );
++operations;
++balance_operations;
}
auto good_it = good_team.begin();
while( good_team.size() > bad_team.size() )
{
good_it = good_team.begin();
bad_team.insert( *good_it );
good_team.erase( *good_it );
++operations;
++balance_operations;
}
int swap_operations = 0;
while( *( good_team.begin() ) < *( bad_team.rbegin() ) )
{
int good_player = *( bad_team.rbegin() );
int bad_player = *( good_team.begin() );
good_team.insert( good_player );
bad_team.insert( bad_player );
good_team.erase( bad_player );
bad_team.erase( good_player );
++operations;
++swap_operations;
}
std::cout << "good team:" << std::endl;
print_set( good_team );
std::cout << std::endl;
std::cout << "bad team:" << std::endl;
print_set( bad_team );
std::cout << std::endl;
std::cout << "completed in " << operations << " operations" << std::endl;
std::cout << "inital sort took " << initial_sort_operations << " operations" << std::endl;
std::cout << "balancing took " << balance_operations << " operations" << std::endl;
std::cout << "swapping took " << swap_operations << " operations" << std::endl;
}