题意:有一个长度为\(n\)的序列,要求在\([1,10^9]\)中找一个\(x\),使得序列中恰好\(k\)个数满足\(\le x\).如果找不到\(x\),输出\(-1\).

题解:先对这个序列排个序,然后首先要注意\(k=0\)的情况

如果\(k=0\)并且序列中含有\(1\),那么我们无论如何都找不到比\(1\)小的数,输出\(-1\),如果不含\(1\),那么只要输出\(a[1]-1\)即可.

如果\(k\ne 0\),那么我们要找前\(k\)个小的数(连续相等的数也算),所以我需要用桶来记录每个数出现的次数,然后遍历序列,累加每个数出现的次数,如果\(sum=k\),那么当前这个数就是我们要找的,如果\(sum>k\)的话,那么我们无论如何都找不到\(x\)(因为\(sum\)记录的是\(\le x\)的数目).

代码:

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <stack>

#include <queue>

#include <vector>

#include <map>

#include <set>

#include <unordered_set>

#include <unordered_map>

#define ll long long

#define fi first

#define se second

#define pb push_back

#define me memset

const int N = 1e6 + 10;

const int mod = 1e9 + 7;

using namespace std;

typedef pair<int,int> PII;

typedef pair<long,long> PLL;

int n,k;

int a[N];

map<int,int> mp;

int main() {

    ios::sync_with_stdio(false);cin.tie(0);

    cin>>n>>k;

     for(int i=1;i<=n;++i){

         cin>>a[i];

         mp[a[i]]++;

     }

     sort(a+1,a+1+n);

     if(k==0){

         if(mp[1]) puts("-1");

         else printf("%d\n",a[1]-1);

         return 0;

     }

     int cnt=0;

     for(auto w:mp){

         cnt+=w.se;

         if(cnt==k){

             printf("%d\n",w.fi);

             return 0;

         }

         if(cnt>k){

             puts("-1");

             return 0;

         }

     }

     puts("-1");

    return 0;

}