Підготовка до різдвяних свят#12289

Підготовка до різдвяних свят (Розбір)

Автор задачі:	Андрій Холод (Connect) , Анна Ярош (Anna_Yarosh)
Підготовлено:	Андрій Холод (Connect)
Розбір:	Андрій Холод (Connect)

Рішення

Давайте зробимо наступний допоміжне введеня. Перетворимо комірочки в які ми маємо ставити гілочки на коробки наступної вмістимості. Перша коробка буде вміщувати ту гілочку яка має бути зверху тобто $1$ далі також $1$ зліва $1$ справа. Іншими словами масив буде наступним: $1, 1, 1, 2, 2, 3, 3, ..., k, k$ 1, 1, 1, 2, 2, 3, 3, ..., k, k.

Тепер давайте заповнювати коробочки наступним чином:

Шукаємо з кінця першу коробку в якій не має гілочки вагою $w_{i}$ w_i.

Тоді якщо в якійсь коробочці переповнення ми можемо перекинути будь яку її підмножину на перед.

Тепер можемо побачити що якщо при такому розділенні не знайдеться префікса на якому сума всіх вмістимостей коробочок менша за кількість гілочок на цьому префіксі то відповідь буде Yes, інакше No

Асимптотика рішення $O (n \cdot l o g (n))$ O(n \cdot log(n)).

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define speed ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define endl '\n'
#define pb push_back

const ll clasik = 2e5+17;

ll w[clasik] , pref[clasik] , poslid[clasik];

void solve() {

    ll n;

    cin>>n;

    for (int i = 1 ; i<=n ; i++) cin>>w[i];

    
    ll nn = n;

    nn--;

    ll k = -1;

    for (int j = 0 ; j*(j+1) <= nn ; j++) {
        if (j*(j+1) == nn) {
            k = j;
            break;
        }
    }

    if (k == -1) {cout<<"No"<<endl; return;}

    sort(w+1 , w+1+n);
    

    vector<ll> v;

    ll len = 1;

    for (int i = 2 ; i<=n ; i++) {
        if (w[i] != w[i-1]) {
            v.pb(len);
            len = 0;
        }
        len++;
    }
    v.pb(len);

    sort(v.begin() , v.end());

    ll p = 0;

    ll cnt = v.size();

    for (int i = 1 ; i<=2*k+1 ; i++) {
        pref[i] = cnt;
        while(p < v.size() && v[p] <= i) {
            p++;
            cnt--;
        }
    }

    reverse(pref+1 , pref+2+2*k);

    poslid[1] = 1;

    ll q = 1;

    for (int i = 1 ; i<=2*k+1 ; i++) {
        poslid[i] = q;
        if (i == 1) continue;
        q+=(i%2);
    }


    ll sum1 = 0, sum2 = 0;

    for (int i = 1 ; i<=n ; i++) {
        sum1+=pref[i];
        sum2+=poslid[i];
        if (sum1 > sum2) {
            cout<<"No"<<endl;
            return;
        }
    }

    if (sum1 == sum2) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return;

}  

signed main() {
    speed;
    int test;
    cin>>test;
    while (test--) solve();
    return 0;
}

C++