c_mt_找有k个数小于自己的数(二分->负责化 / 排序简化)

给出一个序列,序列每个数的范围是 [1, n],找到最小的 x,要求序列中有 k 个数小于 x
有输出 YES,x,否则输出 NO

思路:想问题千万不要太复杂了,能简化就尽量简化。
比如这里的二分用的就不太河里


l = 1, r = n
while l < r:
  m = l +r >> 1
  if chk(m):
    r = m
  else:
    l = m + 1

直接排序就好

#include <bits/stdc++.h>
using namespace std;
void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int &x : a) {
        cin >> x;
    }
    sort(a.begin(), a.end());
    if (k == 0) { //注:特判
        cout << "YES\n";
        cout << 1 << '\n';
    } else {
        int ans = a[k - 1] + 1;
        int t = lower_bound(a.begin(), a.end(), ans) - a.begin();
        if (ans <= n && t == k) {
            cout << "YES\n";
            cout << ans << '\n';
        } else {
            cout << "NO\n";
        }
    }
}
int main() {
    ios_base::sync_with_stdio(false), cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

2021-08-08

上一篇:矩阵快速幂优化dp


下一篇:jeesite 一对多,对子表单独修改时出现 HV000030: No validator could be found for type: