首页 > 其他分享 >【洛谷 P1923】【深基9.例4】求第 k 小的数(快速排序)

【洛谷 P1923】【深基9.例4】求第 k 小的数(快速排序)

时间:2023-12-17 13:01:17浏览次数:42  
标签:P1923 ch 洛谷 int 深基 high read while low

【深基9.例4】求第 k 小的数

题目描述

输入 【洛谷 P1923】【深基9.例4】求第 k 小的数(快速排序)_i++【洛谷 P1923】【深基9.例4】求第 k 小的数(快速排序)_ci_02【洛谷 P1923】【深基9.例4】求第 k 小的数(快速排序)_i++ 为奇数)个数字 【洛谷 P1923】【深基9.例4】求第 k 小的数(快速排序)_ci_04【洛谷 P1923】【深基9.例4】求第 k 小的数(快速排序)_ios_05),输出这些数字的第 【洛谷 P1923】【深基9.例4】求第 k 小的数(快速排序)_i++_06 小的数。最小的数是第 【洛谷 P1923】【深基9.例4】求第 k 小的数(快速排序)_ios_07 小。

请尽量不要使用 nth_element 来写本题,因为本题的重点在于练习分治算法。

输入格式

输出格式

样例 #1

样例输入 #1

5 1
4 3 2 1 5

样例输出 #1

2

思路

先快速排序,然后通过数组索引访问第k小的数。由于数据过大,需要打开O2优化。

AC代码

#include <iostream>
#define AUTHOR "HEX9CF"
using namespace std;

const int maxn = 5000005;
int a[maxn];

void read(int &x)
{
    char ch;
    x = 0;
    while (('0' > ch || '9' < ch))
    {
        ch = getchar();
    }
    while (!('0' > ch || '9' < ch))
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
}

int *particition(int a[], int *low, int *high)
{
    int *l = low, *r = high, pivot = *low;
    while (l < r)
    {
        while (l < r && *r > pivot)
        {
            r--;
        }
        while (l < r && *l <= pivot)
        {
            l++;
        }
        if (l < r)
        {
            swap(*(l++), *(r--));
        }
    }
    if (*l > pivot)
    {
        swap(*(l - 1), *low);
        return l - 1;
    }
    else
    {
        swap(*l, *low);
        return l;
    }
}

void quickSort(int a[], int *low, int *high)
{
    if (low < high)
    {
        int *mid = particition(a, low, high);
        quickSort(a, low, mid - 1);
        quickSort(a, mid + 1, high);
    }
}

int main()
{
    int n, k;
    read(n);
    read(k);
    for (int i = 0; i < n; i++)
    {
        read(a[i]);
    }
    quickSort(a, a, a + n - 1);
    /* for (int i = 0; i < n; i++)
    {
        cout << a[i] << " ";
    } */
    cout << a[k] << endl;
    return 0;
}

标签:P1923,ch,洛谷,int,深基,high,read,while,low
From: https://blog.51cto.com/HEX9CF/8861287

相关文章

  • 洛谷 P9936 [NFLSPC #6] 等差数列
    洛谷传送门对\((i,a_i)\)求出下凸包,那么一条凸包的斜率非正的切线是候选答案。只考虑切凸包上第\(i\)个点的切线,那么斜率的左边界是过凸包第\(i\)和第\(i+1\)个点的直线斜率,右边界是过凸包第\(i-1\)和第\(i\)个点的直线斜率。最优方案的切线斜率一定要么贴着左......
  • 洛谷P1824 进击的奶牛 题解 二分答案
    题目链接:https://www.luogu.com.cn/problem/P1824题目大意:本题相当于在\(n\)个数中选\(c\)个数,使得这\(c\)个数中相差最小的两个数之差尽可能地大。解题思路:我们首先可以给\(a_1\sima_n\)从小到大排一下序(这里有点贪心的思想,你会发现很多涉及贪心的问题在排序之后解......
  • 洛谷 P1217
    原题链接:一开始的思路:把数字转换成字符串类型并将字符串反转,若反转后的字符串和原来的字符串一致且该数是质数,则是回文质数。#include<bits/stdc++.h>usingnamespacestd;boolisPrime(intx){if(x<2)returnfalse;for(inti=2;i<=x/i;i++){......
  • 【洛谷 P1271】【深基9.例1】选举学生会 题解(计数排序)
    【深基9.例1】选举学生会题目描述学校正在选举学生会成员,有名候选人,每名候选人编号分别从1到,现在收集到了张选票,每张选票都写了一个候选人编号。现在想把这些堆积如山的选票按照投票数字从小到大排序。输入格式输入和以及个选票上的数字。输出格式求出排序后的选票编......
  • [NOIP2010 提高组] 关押罪犯 - 洛谷
    P1525[NOIP2010提高组]关押罪犯-洛谷|计算机科学教育新生态(luogu.com.cn)种类并查集#include<bits/stdc++.h>#definedebug(a)cout<<#a<<"="<<a<<'\n';usingnamespacestd;usingi64=longlong;typedefpair<i64,i64>......
  • 洛谷P3396 哈希冲突
    根号分治模板题#include<iostream>#include<stdio.h>#include<algorithm>#include<cstring>#include<cmath>#defineRED"\033[0;32;31m"#defineNONE"\033[m"#defineR(x)x=read()#defineFor(i,j,n)for......
  • 洛谷P4199 万径人踪灭
    题目链接考虑容斥:拿满足条件\(1\)的方案数减去满足条件\(1\)但不满足条件\(2\)的方案数就是答案。满足条件\(1\)但不满足条件\(2\)的方案可以用\(\text{Manacher}\)算法\(O(n)\)计算。对于满足条件\(1\)的总方案数,我们记\(c_i\)表示以\(i\)位置为对称轴时,......
  • 「杂题乱刷」洛谷P1216
    题目链接一道dp的入门题。\(O(2^n)\):考虑直接爆搜,可以考虑到所有情况。\(O(n^2)\):考虑\(dp\),设\(dp_{i,j}\)代表到达第\(i\)层第\(j\)个数所能达到的最大值。状态转移方程为\(dp_{i,j}=a_{i,j}+\max(dp_{i-1,j-1},dp_{i-1,j})\)。最终答案就是\(\max(dp_{n,1},d......
  • 【洛谷 P2670】[NOIP2015 普及组] 扫雷游戏 题解(模拟)
    [NOIP2015普及组]扫雷游戏题目背景NOIP2015普及组T2题目描述扫雷游戏是一款十分经典的单机小游戏。在行列的雷区中有一些格子含有地雷(称之为地雷格),其他格子不含地雷(称之为非地雷格)。玩家翻开一个非地雷格时,该格将会出现一个数字——提示周围格子中有多少个是地雷格。游戏的......
  • 【LGR-168-Div.4】洛谷入门赛 #18
    打表过样例题目描述很不幸,你遇到了不负责任的出题人。在某道试题里,共有\(N\)个测试点,组成了\(k\)个Subtask,第\(i\)个Subtask包含\(p_i\)个测试点,第\(j\)个测试点的编号为\(w_{i,j}\)。请注意,一个测试点可能属于多个Subtask。Subtask每个Subtask包含多个测......