美团笔试 8.8

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int N, K;


int main(){
    
    int T ;
    cin>>T;
    while(T--){
        cin>>N >> K;
        vector<int> data(N);
        for(int i=0;i<N;i++)
            cin >> data[i];
        sort(data.begin(), data.end());

        int ans;

        if(K>N){
            cout<< "NO" <<endl;
            continue; 
        }

        if(K==0)
            ans = 1;
        else
            ans = data[K-1] + 1;
        
        if(ans < 1 || ans > N){
            cout<<"NO"<<endl;
            continue;
        }
        
        if(K<N && data[K-1]==data[K]){
            cout<< "NO" <<endl;
            continue;
        }
        
        cout<<"YES"<<endl;
        cout<<ans<<endl;
    }
}

#include<iostream>
#include<vector>

using namespace std;

int main(){
    string str;
    getline(cin,str);
    string ret;
    for(int i=0 ; i<str.size() ;i++){
        if(str[i] == ' ')
            continue;
        else{
            ret+=str[i];
            int tmp = i+1;
            while( tmp <str.size() && (str[tmp] == str[i] || str[tmp] == ' ') )
                tmp++;
            i = tmp-1;
        }
    }
    cout<<ret<<endl;
    return 0;
}

#include<iostream>
#include<vector>
#include<set>
using namespace std;

int main(){
    int N;
    cin>>N;
    vector<int> data(N);
    for(int i=0;i<N;i++)
        cin>>data[i];
    
    set<int> s;
    int ans = 0;

    
    for(int i=0;i<N;i++){
        auto it = s.lower_bound(data[i]);
        if(it != s.begin()){
            ans += (*(--it) * (i+1));
        }
        s.insert(data[i]);
    }

    cout<< ans <<endl;
    return 0;
}

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int getIndex(vector<int>& tree , int num){
    int l = 0 , r = tree.size() -1;
    while(l<r){
        int mid = (l+r)>>1;
        if(tree[mid] == num)
            return mid;
        if(tree[mid] > num)
            r = mid;
        else
            l = mid + 1;
    }
    return l;
}

int findroot(vector<int> & tree , int x){
    if(tree[x] != -1){
        tree[x] = findroot(tree,tree[x]);
        return tree[x];
    }else
        return x;
}

int main(){
    int N;
    cin>>N;
    vector<int> data(N);
    for(int i=0;i<N;i++)
        cin>>data[i];

    vector<int> tmp(data);
    sort(tmp.begin(),tmp.end());
    tmp.erase( unique(tmp.begin(),tmp.end()) , tmp.end());
    
    vector<int> tree(tmp.size(),-1);

    int ans = 0;

    for(int i=0;i<N/2 ;i++){
        if(data[i] != data[i+N/2]){
            int x = getIndex(tmp,data[i]) , y = getIndex(tmp,data[i+N/2]);
            int xroot = findroot(tree,x) , yroot = findroot(tree,y);
            if(xroot!=yroot){
                tree[xroot] = yroot;
                ans++;
            }
        }
    }
    cout<< ans <<endl;
    return 0;
}

#include<iostream>
#include<vector>
#include<stack>
using namespace std;


typedef struct node{
    struct node* left;
    struct node* right;
    int val;
    node():left(nullptr) , right(nullptr) ,val(0){}
    node(int v):left(nullptr) , right(nullptr) ,val(v){}
}Node;

vector<Node*> Tree;

void createTree(vector<pair<int,int>>& data , Node* root){
    Tree[root->val] = root;
    int l = data[root->val].first , r = data[root->val].second;
    if(l){
        root->left = new Node(l);
        createTree(data,root->left);
    }
    if(r){
        root->right = new Node(r);
        createTree(data,root->right);
    }
}

int main(){
    int N,M,K;
    cin>>N>>M>>K;
    vector<pair<int,int>> data(N+1);
    Tree.resize(N+1);
    for(int i=1;i<=N;i++)
        cin>>data[i].first >> data[i].second;
    Node* root = new Node(K);
    createTree(data,root);

    while(M--){
        int t;
        cin>>t;
        Node* tmp = Tree[t]->left;
        Tree[t]->left = Tree[t]->right;
        Tree[t]->right = tmp; 
    }

    stack<Node*> s;
    while(!s.empty() || root){
        while(root){
            s.push(root);
            root = root->left;
        }

        Node* tmp = s.top() ; s.pop();
        cout<<tmp->val << " ";
        root = tmp->right;
    }
    cout<<endl;
    return 0;
}