PAM !#12251

PAM ! (Corrigé)

Auteur du problème :	Hasan Saleh (MathModel)
Préparé par :	Hasan Saleh (MathModel)
Édité par :	Hasan Saleh (MathModel)

Solution

Nous ne nous soucions que des paires qui s'additionnent à $k$ , nous devons construire la plus longue séquence d'entiers où $a_{i} + a_{i + 1} = k$ a_i+a_{i+1}=k pour le plus grand nombre d'indices $i$ dans cette séquence.

Tout d'abord, nous prenons toutes les paires distinctes $(x, y)$ qui s'additionnent à $k$ , où $cnt (x), cnt (y) \geq 1$ \text{cnt}(x),\text{cnt}(y) \ge 1, la construction optimale sera $x, y, x, y, x, y, ...$ x,y,x,y,x,y,... où la longueur de celle-ci est $min (cnt (x), cnt (y))$ \min(\text{cnt}(x),\text{cnt}(y)), dans le cas idéal ce sera $⌊ 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} cependant, si nous avons des fréquences formant des parties différentes, alors nous devons laisser celui avec un élément supplémentaire à la fin, en commençant par l'élément avec l'élément supplémentaire.

Nous faisons de même pour toutes les paires $(x, y)$ telles que $x + y = k$ x+y=k, et les autres éléments sont sans importance, donc ils peuvent être mis dans n'importe quel ordre.

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

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