Milad Bayramına Hazırlıq#12289

Milad Bayramına Hazırlıq (Həll təhlili)

Məsələnin müəllifləri:	Andrey Xolod (Connect), Anna Yaroş (Anna_Yarosh)
Hazırlayan:	Andrey Xolod (Connect)
Təhlil:	Andrey Xolod (Connect)

Həll

Gəlin aşağıdakı köməkçi təsviri edək. Vətikləri yerləşdirməli olduğumuz xanaları müəyyən tutumlara malik qutular kimi təsəvvür edək. Birinci qutu ən üstdə olmalı budağı — yəni $1$ — saxlayacaq, daha sonra solda $1$ , sağda $1$ olacaq. Başqa sözlə, tutum massivi belə olacaq: [1, 1, 1, 2, 2, 3, 3, ..., k, k.]

İndi qutuları belə dolduraq:

Sondan başlayaraq, hələ də $w_{i}$ w_i ağırlığında budaq olmayan ilk qutunu tapırıq.

Əgər hansısa qutu artıq dolarsa, onun istənilən alt çoxluğunu əvvələ keçirmək mümkündür.

İndi görürük ki, belə bölmədə elə bir prefiks **tapılmırsa** ki, həmin prefiksdəki qutuların ümumi tutumu **orada olan budaqların sayından az olsun**, onda cavab **Yes**, əks halda **No** olacaq.

Həllin asimptotik mürəkkəbliyi — (O(n 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++