1

Тема: 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;
}

2

Re: e-olymp 609

https://uk.wikipedia.org/wiki/%D0%97%D0 … 0%BA%D0%B0

Подякували: Betterthanyou1

3 Востаннє редагувалося koala (07.03.2020 00:02:54)

Re: e-olymp 609

ur_naz, блиснули? Тут навіть O(n^2) не проходить.
Eff1c, після сортування ідете по масиву з двох боків. Якщо сума менша за k - просувається з обох боків, якщо більша - лише з більшого. Кількість кроків - розв'язок. Усе. Складність O(n)+складність сортування, тобто O(n log n).

Подякували: Eff1c1

4

Re: e-olymp 609

гарантуєте оптимальність? щось дуже сумнівно

5 Востаннє редагувалося koala (06.03.2020 23:25:31)

Re: e-olymp 609

O(n log n). Маєте кращі думки? Поки що ви лише NP-повний розв'язок пропонували.

Подякували: leofun011

6 Востаннє редагувалося koala (07.03.2020 08:58:41)

Re: e-olymp 609

Прихований текст
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main() {
    int n, k;
    cin>>n>>k;
    std::vector<int> arr(n);
    for(int i=0; i<n; ++i)
    {
        cin>>arr[i];
        if(arr[i]>k) {
            cout<<"Impossible";
            return 0;
        }
    }
 
    sort(arr.begin(), arr.end());
 
    int bigger = n-1;
    int lesser = 0;
    int count = 0;
    while(bigger>=lesser)
    {
        ++count;
        if(arr[bigger]+arr[lesser]<=k)
            ++lesser;
        --bigger;
    }
 
    cout << count;
    return 0;
}

Все проходить.

Подякували: leofun01, Eff1c, Betterthanyou3

7

Re: e-olymp 609

Перше ввід, потім сортування, а потім логіка. То не забагато?
Чого при вводі не зробити наприклад деревовидне сортування. Чи зразу не пробувати видаляти ті пари де сума рівна k.

Подякували: leofun01, Eff1c2

8

Re: e-olymp 609

я лише дав напрямок для роздумів. терпіти не можу, коли вирішують олімпіадні задачі

9 Востаннє редагувалося koala (07.03.2020 10:35:35)

Re: e-olymp 609

Vo_Vik написав:

Перше ввід, потім сортування, а потім логіка. То не забагато?
Чого при вводі не зробити наприклад деревовидне сортування. Чи зразу не пробувати видаляти ті пари де сума рівна k.

Складність не змінюється, нащо?
Я бачу тут купу можливостей провести дрібні оптимізації. Наприклад, коли ліва чи права межа перетинає значення k/2, можна далі не рухатися, а додати розмір шматка, що лишився (якщо всі менші за k/2 - поділений на 2). У мене є сильне враження, що ще щось можна виграти, якщо одразу розкладати у два дерева відносно k/2 - але це все не змінює складності, а тести і так проходить.

Подякували: leofun01, Eff1c2

10

Re: e-olymp 609

Дякую)
Чим відрізняється звичайне оголошення масиву від

std::vector<int> arr(n);

?

11

Re: e-olymp 609

Тут звичайний масив, дійсно, трохи краще підходить.
Вектор можна динамічно змінювати, але тут це не має значення.

Подякували: Eff1c1

12

Re: e-olymp 609

Протестував на std::multiset (без видалення) - стало повільнішим. Можливо, якщо самому дерево реалізувати...