ალექსანდრე აკეთებს თოვლის ბაბუებს. თითოეული თოვლის ბაბუა კეთდება ზუსტად 3 თოვლის გუნდისაგან: დიდი, საშუალო და პატარა. თითოეულ ნაკეთობაში არ უნდა გვხვდებოდეს ერთნაირი რადიუსის გუნდები , ანუ სამივე გუნდის რადიუსები წყვილ-წყვილად განსხვავებულებია . მაგალითად , გუნდებით , რომელთა რადიუსებია 1 , 2 და 3 შეგვიძლია თოვლის ბაბუის გაკეთება, მაგრამ 2 ,2 3 -ით ან 2 2 2 -ით არა . დაეხმარეთ ალექსანდრეს, გაიგოს რა მაქსიმალური რაოდენობის თოვლის ბაბუების გაკეთება შეუძლია მოცემული გუნდებით.
შემომავალი ინფორმაცია:
პირველ ხაზზე შემოდის 1 რიცხვი n (1<= n <=105)- თოვლის გუნდათა რაოდენობა .
შემდეგი ხაზზე შემოდის n ცალი რიცხვი (r)- გუნდათა რადიუსები (1<= r <= 109). რადიუსები შეიძლება განმეორდეს .
პასუხი :
პირველ ხაზზე გამოიტანეთ რიცხვი k - გაკეთებული თოვლის ბაბუების მაქსიმალური რაოდენობა , შემდეგ k ხაზზე კი თითოეული თოვლის ბაბუის აღწერა - დიდი, საშუალო და პატარა გუნდათა რადიუსები, რომლითაც ეს თოვლის ბაბუა გაკეთდა. თუ ამოხსნის რამოდენიმე ვარიანტია , დაბეჭდეთ ნებისმიერი .
მაგალითი 1 :
Input :
7
1 2 3 4 5 6 7
Output :
2
1 2 3
4 5 6
მაგალითი 2 :
Input :
3
4 4 3
Output
0
დავითვალოთ რამდენჯერ გვხვდება თითოეული რადიუსი და ჩავყაროთ priority-queue ში, ამის შემდეგ ყოველ ჯერზე , იქამდე სანამ რიგის ზომა 3 ან მეტია, ამოვიღოთ, ზედა სამი რადიუსი, გავაკეთოთ თოვლის ბაბუა, დავაკლოთ რაოდენობებს 1 და რომელი რადიუსებიც ისევ დაგვრჩება უკან დავაბრუნოთ რიგში შეცვლილი რაოდენობით.
ამოხსნის კოდი
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n , big[40000] ,medium[40000] ,small[40000] , x ,nums[110000] ,counter= 0 ;
cin >> n;
priority_queue<pair<int, int > > pq;
map<int, int> m;
for(int i = 0; i < n; i++) {
cin>>x; m[x] += 1;
if(m[x] == 1) {
nums[counter] = x;
counter++;
}
}
for(int i = 0; i < counter; i++) {
pair<int, int> k;
k.first = m[nums[i]];
k.second = nums[i];
pq.push(k);
}
int res = 0, b[3];
while(pq.size() > 2) {
pair<int,int> v1=pq.top(); pq.pop(); b[0]=v1.second;
pair<int,int> v2=pq.top(); pq.pop(); b[1]=v2.second;
pair<int,int> v3=pq.top(); pq.pop(); b[2]=v3.second;
sort(b,b+3);
big[res] = b[2];
medium[res] = b[1];
small[res] = b[0];
res++;
if(v1.first != 1) {
v1.first--;
pq.push(v1);
}
if(v2.first != 1) {
v2.first--;
pq.push(v2);
}
if(v3.first != 1) {
v3.first--;
pq.push(v3);
}
}
cout << res << endl;
for(int i = 0; i < res; i++) {
cout << big[i] << " " << medium[i] << " " << small[i] << endl;
}
return 0;
}