Тема: e-olymp 609
https://www.e-olymp.com/uk/problems/609
Написав код до задачки, а він не проходить (частково із-за часу, частково із-за неправильних відповідей).
#include <iostream>
#include <stdlib.h>
using namespace std;
int comp (const int *i, const int *j) // компаратор для сортування по спаданню
{
return *j - *i;
}
int main()
{
int x=0, n, k, tmp; // x - кількість разів, n - кількість каністр, k - максимальна кількість літрів, tmp - не пам'ятаю для чого створив, але тепер без нього програма видає менше правильних відповідей
cin >> n >> k;
int arr[n];
for(int i=0; i<n; i++)
{
cin >> arr[i];
if (arr[i]>k) // якщо є каністра, яка перевищує максимальний літраж
{
cout << endl << "Impossible";
return 0;
}
}
qsort(arr,n, sizeof (int), (int(*) (const void *, const void *)) comp); // сортуємо
for(int i=0; i<n;i++)
{
if (arr[i]!=0) // перевіряємо чи елемент не = 0, тому що коли переносимо каністру, то значення елементу змінюємо на 0
{
x++; // в будь-якому випадку ми зробимо 1 похід (чи з 1 каністрою чи з 2ма)
if (arr[i] < k) // якби дана каністра (елемент масиву) = максимальному літражу ми б за похід перенесли б 1 каністру
{ // а якщо менша ніж k (максимальна кількість літрів) то спробуємо підібрати пару, щоб перенести 2
for (int m=i+1; m < n; m++) // перебираємо кожен наступний (після даного) елемент (P`S.нагадую, що масив відсортований по спаданню)
{
if (arr[m]==0) continue; // якщо елемент = 0, то ми вже його перенесли, переходимо до наступного
if (arr[m] + arr[i] <= k) // якщо сума двох каністр <= максимальному літражу
{
arr[m] = 0; // присвоюємо елементу значення 0
break; // завершуємо цикл підбирання пари
}
}
}
}
}
cout << x;
return 0;
}