PAM!#12251

PAM! (Həll təhlili)

Problemin Müəllifi:	Hasan Saleh (MathModel)
Hazırlayan:	Hasan Saleh (MathModel)
Redaktə edən:	Hasan Saleh (MathModel)

Həll

Biz yalnız $k$ -ya bərabər olan cütlüklərlə maraqlanırıq, $a_{i} + a_{i + 1} = k$ a_i+a_{i+1}=k olan indekslərin sayını maksimuma çatdıran ən uzun tam ədəd ardıcıllığını qurmalıyıq.

İlk öncə, $k$ -ya bərabər olan bütün fərqli cütlükləri $(x, y)$ seçirik, burada $cnt (x), cnt (y) \geq 1$ \text{cnt}(x),\text{cnt}(y) \ge 1 , optimal quruluş $x, y, x, y, x, y, ...$ x,y,x,y,x,y,... olacaq, burada onun uzunluğu $min (cnt (x), cnt (y))$ \min(\text{cnt}(x),\text{cnt}(y))-dir, ideal halda bu $⌊ m i n (cnt(x), cnt (y)) /2 ⌋ x, y, x, y, ..., x, y$ \underbrace{x,y,x,y,...,x,y}_{\lfloor \min(\text{cnt(x)},\text{cnt}(y))/2 \rfloor} olacaq, lakin əgər fərqli partiyaları formalaşdıran tezliklərimiz varsa, onda əlavə elementi olanı sona qoymalıyıq, əlavə elementi olan elementdən başlayaraq.

Biz $x + y = k$ x+y=k olan bütün cütlüklər üçün eyni şeyi edirik, qalan elementlər isə əhəmiyyətsizdir, ona görə də istənilən sırada yerləşdirilə bilər.

#include <bits/stdc++.h>
using namespace std;
#define ll long long 

void solve(){
    int n,k;cin>>n>>k;
    vector<int>a(n);
    for(auto &i:a)cin>>i;
    map<int,int>mp;
    for(auto i:a)mp[i]++;
    set<pair<int,int>>pairs;
    for(auto i:a){
        if(mp[i]&&mp[k-i]){
            pairs.insert({i,k-i});
        }
    }
    vector<int>b;
    for(auto p:pairs){
        if(p.first==p.second){
            continue;
        }
        if(mp[p.first]>mp[p.second]){
            swap(p.first,p.second);
        }
        while(mp[p.first]>0){
            b.push_back(p.second);
            b.push_back(p.first);
            mp[p.second]--;
            mp[p.first]--;
        }
        while(mp[p.second]>0){
            b.push_back(p.second);
            mp[p.second]--;
        }
    }
    for(auto i:pairs){
        if(i.first==i.second){
            while(mp[i.first]){
                b.push_back(i.first);
                mp[i.first]--;
            }
        }
    }
    for(auto i:mp){
        while(mp[i.first]){
            b.push_back(i.first);
            mp[i.first]--;
        }
    }
    for(auto i:b){
        cout<<i<<" ";
    }
    cout<<"\n";
}


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t=1;cin>>t;
    while(t--){
        solve();
    }
}

C++

Komplekslik $O (n lo g n)$ \mathcal{O}(n \log n).