PAM!#12251

PAM! (Розбір)

Автор проблеми:	Hasan Saleh (MathModel)
Підготовлено:	Hasan Saleh (MathModel)
Редаговано:	Hasan Saleh (MathModel)

Рішення

Нам важливі лише пари, які в сумі дають $k$ , нам потрібно побудувати найдовшу послідовність цілих чисел, де $a_{i} + a_{i + 1} = k$ a_i+a_{i+1}=k для найбільшої кількості індексів $i$ у цій послідовності.

По-перше, ми вибираємо всі різні пари $(x, y)$ , які в сумі дають $k$ , де $cnt (x), cnt (y) \geq 1$ \text{cnt}(x),\text{cnt}(y) \ge 1, оптимальна конструкція буде $x, y, x, y, x, y, ...$ x,y,x,y,x,y,..., де довжина її $min (cnt (x), cnt (y))$ \min(\text{cnt}(x),\text{cnt}(y)), в ідеальному випадку це буде $⌊ 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}, однак якщо у нас є частоти, що формують різні партії, тоді ми повинні залишити елемент з додатковим елементом в кінці, починаючи з елемента з додатковим елементом.

Ми робимо те ж саме для всіх пар $(x, y)$ , що $x + y = k$ x+y=k, а решта елементів не мають значення, тому їх можна розташувати в будь-якому порядку.

#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++

Складність $O (n lo g n)$ \mathcal{O}(n \log n).