¡PAM!#12251

¡PAM! (Editorial)

Autor del problema:	Hasan Saleh (MathModel)
Preparado por:	Hasan Saleh (MathModel)
Editado por:	Hasan Saleh (MathModel)

Solución

Solo nos importan los pares que suman $k$ , necesitamos construir la secuencia más larga de enteros donde $a_{i} + a_{i + 1} = k$ a_i+a_{i+1}=k para la mayor cantidad de índices $i$ en esa secuencia.

Primero, elegimos todos los pares distintos $(x, y)$ que suman $k$ , donde $cnt (x), cnt (y) \geq 1$ \text{cnt}(x),\text{cnt}(y) \ge 1, la construcción óptima será $x, y, x, y, x, y, ...$ x,y,x,y,x,y,... donde la longitud de esto es $min (cnt (x), cnt (y))$ \min(\text{cnt}(x),\text{cnt}(y)), en el caso ideal será $⌊ 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} sin embargo, si tenemos frecuencias que forman diferentes partes, entonces debemos dejar el que tiene un elemento extra al final, comenzando desde el elemento con el elemento extra.

Hacemos lo mismo para todos los pares $(x, y)$ que $x + y = k$ x+y=k, y el resto de los elementos son irrelevantes, por lo que se pueden colocar en cualquier orden.

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

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