Jak zrobić tak, żeby nie było przekroczonej pamięci?
Partycja postanowiła włączyć się do pewnej akcji. Grupa jej przyjaciół prowadzi eksperyment nad wydajnością badań grupy naukowców. Obecnie pracują nad nowymi metodami walki z globalnym ociepleniem. Ponieważ katastrofa może nastąpić lada moment trzeba działać szybko. Badacze muszą zostać rozdzieleni na dwie grupy pracujące równolegle. Okazuje się, że właśnie to jest kluczową sprawą dla wydajności. Partycja otrzymała listę naukowców składającą się z imienia, nazwiska oraz punktów zdolności badawczych. Im punktacja jest wyższa tym zdolniejszy jest dany naukowiec. Badacze są jednak niezwykle przywiązani do swoich miejsc. Siedzą przy okrągłym stole zawsze w takiej samej kolejności jaki prezentuje lista. Partycja musi ich podzielić na dwie równe grupy. Należy jednak pamiętać, że różnica między najzdolniejszym oraz najmniej zdolnym naukowcem powinna być jak najmniejsza i absolutnie nie może przekraczać ściśle określonej wartości. Mogłoby to spowodować konflikty w zespole. Ważniejsze są jednak średnie zdolności każdego zespołu która powinny być możliwie najrówniejsze. Zawsze może się zdarzyć sytuacja w której zespół można podzielić na więcej niż jeden sposób dlatego nasza bohaterka musi wykonać swoją pracę zgodnie ze ściśle określoną procedurą. Podzieli stół na dwie równe połowy względem otrzymanej listy. Następnie będzie przesuwała się o jedną osobę zgodnie z kierunkiem ruchu zegara. Pierwsze najlepsze rozwiązanie zostaje uznane za właściwy podział. Co ważne liczba naukowców zawsze jest parzysta. Ponieważ pracę należy wykonywać codziennie bo pracownicy często się zmieniają Partycji przydałby się program który zautomatyzuje pracę.
Wejście:
W pierwszej linii wejścia program otrzymuje liczbę n oznaczającą ilość naukowców oraz v będącą maksymalną różnicą zdolności naukowców w zespole. Następnie w n liniach program otrzymuje dane naukowców zgodnie z ruchem wskazówek zegara, składające się z dwóch ciągu znaków f oraz s będących imieniem i nazwiskiem naukowca oraz liczbę naturalną i oznaczającą zdolność.
Wyjście:
Na wyjściu program powinien wyświetlić dwie listy naukowców oddzielone spacją. Listy powinny być wyświetlone w kierunku zgodnym z kierunkiem wprowadzania. Jeżeli naukowców nie da się podzielić zgodnie z wytycznymi należy wyświetlić słowo „NIE”.
1 ≤ n ≤ 100000
1 ≤ i ≤ 1000
Przykładowe wejście:
6 5
Jan Nowak 12
Wojciech Kowalski 11
Irena Krawiec 1
Marcin Janowski 3
Krystian Król 2
Joanna Malinowska 10
Przykładowe wyjście:
Irena Krawiec
Marcin Janowski
Krystian Król
Joanna Malinowska
Jan Nowak
Wojciech Kowalski
Uwaga:
Rozwiązanie ma wykorzystywać samodzielną implementację kolejki bez wykorzystania bibliotek STL.
#include <iostream>
#include <string>
using namespace std;
struct Element{
string name;
string surname;
int num = 0;
Element *after = nullptr;
Element(string name, string surname, int num):name(name), surname(surname), num(num), after(nullptr){}
};
class Kolejka{
Element *first = nullptr;
Element *last = nullptr;
int sum = 0;
int max_ = 0, min_ = 0;
public:
void push_back(string name, string surname, int num){
Element *n = new Element(name, surname, num);
sum += num;
if(this->first == nullptr || this->last == nullptr){
this->first = this->last = n;
max_ = min_ = num;
}
else{
this->last->after = n;
this->last = n;
if(num > max_)
max_ = num;
if(num < min_)
min_ = num;
}
}
void show(){
Element *temp = this->first;
while(temp != nullptr){
cout << temp->name << " " << temp->surname << endl; //" " << temp->num << endl;
temp = temp->after;
}
}
int min(){
Element *temp = this->first;
int min = temp->num;
while(temp != nullptr){
if(min > temp->num) min = temp->num;
temp = temp->after;
}
return min;
}
int max(){
Element *temp = this->first;
int max = temp->num;
while(temp != nullptr){
if(max < temp->num) max = temp->num;
temp = temp->after;
}
return max;
}
void pop_front(){
Element * temp = this->first;
this->first = this->first->after;
sum -= temp->num;
if(temp->num == min_)
min_ = min();
if(temp->num == max_)
max_ = max();
}
Element *front(){
return first;
}
int getSum(){
return this->sum;
}
int getMin(){
return this->min_;
}
int getMax(){
return this->max_;
}
};
int main()
{
Kolejka A, B;
int n, v, i;
string name, surname;
bool check = false;
cin >> n >> v;
for(int j = 0; j < n; ++j){
cin >> name >> surname >> i;
if(j < n / 2){
A.push_back(name, surname, i);
}
else{
B.push_back(name, surname, i);
}
}
n /= 2;
int pm = 0;
int roznica_sum = 0;
int min_roznica = -3;
for(int s = 0; s < n; ++s){
Element *temp1, *temp2;
temp1 = A.front();
temp2 = B.front();
B.push_back(temp1->name, temp1->surname, temp1->num);
A.pop_front();
A.push_back(temp2->name, temp2->surname, temp2->num);
B.pop_front();
if(A.getMax() - A.getMin() < v && B.getMax() - B.getMin() < v){
check = true;
roznica_sum = abs(A.getSum() - B.getSum());
if(min_roznica > roznica_sum || min_roznica == -3){
min_roznica = roznica_sum;
pm = s;
}
}
}
if(check == false){
cout << "NIE" << endl;
}
else{
for(int l = 0; l <= pm; ++l){
Element *temp1, *temp2;
temp1 = A.front();
temp2 = B.front();
B.push_back(temp1->name, temp1->surname, temp1->num);
A.pop_front();
A.push_back(temp2->name, temp2->surname, temp2->num);
B.pop_front();
}
B.show();
cout << endl;
A.show();
}
//cout << " Sriednia B " << sriednia_B << " minB ";// << min_B << " maxB " << max_B << endl;
//cout << "BBB/////////////////////////BBB" << endl;
//B.show();
//cout << " Sriednia A " << sriednia_A << " minA ";// << min_A << " maxA " << max_A<< endl;
//cout << "AAA/////////////////////////AAA " << endl;
//A.show();
return 0;
}
