#1133 : 二分·二分查找之k小数 ( 快速排序, 分治 OR nth_element() 函数)

2024-08-30 21:08

本文主要是介绍#1133 : 二分·二分查找之k小数 ( 快速排序, 分治 OR nth_element() 函数),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!


#1133 : 二分·二分查找之k小数
时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

在上一回里我们知道Nettle在玩《艦これ》,Nettle的镇守府有很多船位,但船位再多也是有限的。Nettle通过捞船又出了一艘稀有的船,但是已有的N(1≤N≤1,000,000)个船位都已经有船了。所以Nettle不得不把其中一艘船拆掉来让位给新的船。Nettle思考了很久,决定随机选择一个k,然后拆掉稀有度第k小的船。 已知每一艘船都有自己的稀有度,Nettle现在把所有船的稀有度值告诉你,希望你能帮他找出目标船。

提示:非有序数组的二分查找之二
输入

第1行:2个整数N,k。N表示数组长度,
第2行:N个整数,表示a[1..N],保证不会出现重复的数,1≤a[i]≤2,000,000,000。
输出

第1行:一个整数t,表示t在数组中是第k小的数,若K不在数组中,输出-1。
样例输入

10 4
1732 4176 2602 6176 1303 6207 3125 1 1011 6600

样例输出

1732

//快排分治,选择一半排序 31ms
#include<cstdio>
#include<algorithm>
//#include<bits/stdc++.h>
using namespace std;
template<class T>inline T read(T&x)
{char c;while((c=getchar())<=32)if(c==EOF)return 0;bool ok=false;if(c=='-')ok=true,c=getchar();for(x=0; c>32; c=getchar())x=x*10+c-'0';if(ok)x=-x;return 1;
}
template<class T> inline T read_(T&x,T&y)
{return read(x)&&read(y);
}
template<class T> inline T read__(T&x,T&y,T&z)
{return read(x)&&read(y)&&read(z);
}
template<class T> inline void write(T x)
{if(x<0)putchar('-'),x=-x;if(x<10)putchar(x+'0');else write(x/10),putchar(x%10+'0');
}
template<class T>inline void writeln(T x)
{write(x);putchar('\n');
}
//-------ZCC IO template------
const int maxn=1000011;
const double inf=999999999;
#define lson (rt<<1),L,M
#define rson (rt<<1|1),M+1,R
#define M ((L+R)>>1)
#define For(i,t,n) for(int i=(t);i<(n);i++)
typedef long long  LL;
typedef double DB;
typedef pair<int,int> P;
#define bug printf("---\n");
#define mod 10007
LL a[maxn];
LL k;
void my_sort(LL left,LL right)
{// for(int i=left;i<right;i++)//  printf("%d ",a[i] );// printf("\n");if(left<right){LL key=a[left];LL low=left;LL high=right;while(low<high){while(low<high&&a[high]>=key)high--;if(low<high)swap(a[high],a[low]);while(low<high&&a[low]<=key)low++;if(low<high)swap(a[high],a[low]);}//  printf("[k==%lld , left =%lld  right=%lld ]\n",k,low,high);if(low==k)return ;//选择一半进行排序即可if(k<low)my_sort(left,low-1);elsemy_sort(low+1,right);}
}
int main()
{//#ifndef ONLINE_JUDGE//freopen("in.txt","r",stdin);//#endif // ONLINE_JUDGELL n,m,i,j,t;while(read_(n,k)){For(i,1,n+1){read(a[i]);}// nth_element(a,a+k-1,a+n);my_sort(1,n);if(k<=0||k>n)puts("-1");elsewriteln(a[k]);}return 0;
}<pre name="code" class="cpp">//直接调用C++ STL函数 nth_element(start,start+k,end);  33ms
#include<cstdio>
#include<algorithm>
//#include<bits/stdc++.h>
using namespace std;
template<class T>inline T read(T&x)
{char c;while((c=getchar())<=32)if(c==EOF)return 0;bool ok=false;if(c=='-')ok=true,c=getchar();for(x=0; c>32; c=getchar())x=x*10+c-'0';if(ok)x=-x;return 1;
}
template<class T> inline T read_(T&x,T&y)
{return read(x)&&read(y);
}
template<class T> inline T read__(T&x,T&y,T&z)
{return read(x)&&read(y)&&read(z);
}
template<class T> inline void write(T x)
{if(x<0)putchar('-'),x=-x;if(x<10)putchar(x+'0');else write(x/10),putchar(x%10+'0');
}
template<class T>inline void writeln(T x)
{write(x);putchar('\n');
}
//-------ZCC IO template------
const int maxn=1000011;
const double inf=999999999;
#define lson (rt<<1),L,M
#define rson (rt<<1|1),M+1,R
#define M ((L+R)>>1)
#define For(i,t,n) for(int i=(t);i<(n);i++)
typedef long long  LL;
typedef double DB;
typedef pair<int,int> P;
#define bug printf("---\n");
#define mod 10007
LL a[maxn];
LL k;
int main()
{LL n,m,i,j,t;while(read_(n,k)){For(i,0,n){read(a[i]);}nth_element(a,a+k-1,a+n);if(k<0||k>n)puts("-1");elsewriteln(a[k-1]);}return 0;
}

 


这篇关于#1133 : 二分·二分查找之k小数 ( 快速排序, 分治 OR nth_element() 函数)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1121935

相关文章

好题——hdu2522(小数问题:求1/n的第一个循环节)

好喜欢这题,第一次做小数问题,一开始真心没思路,然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数,不能写作两整数之比*****************************(一开始没想到,小学没学好) 此题1/n肯定是一个有限循环小数,了解这些后就能做此题了。 按照除法的机制,用一个函数表示出来就可以了,代码如下

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

hdu2289(简单二分)

虽说是简单二分,但是我还是wa死了  题意:已知圆台的体积,求高度 首先要知道圆台体积怎么求:设上下底的半径分别为r1,r2,高为h,V = PI*(r1*r1+r1*r2+r2*r2)*h/3 然后以h进行二分 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#includ

电脑桌面文件删除了怎么找回来?别急,快速恢复攻略在此

在日常使用电脑的过程中,我们经常会遇到这样的情况:一不小心,桌面上的某个重要文件被删除了。这时,大多数人可能会感到惊慌失措,不知所措。 其实,不必过于担心,因为有很多方法可以帮助我们找回被删除的桌面文件。下面,就让我们一起来了解一下这些恢复桌面文件的方法吧。 一、使用撤销操作 如果我们刚刚删除了桌面上的文件,并且还没有进行其他操作,那么可以尝试使用撤销操作来恢复文件。在键盘上同时按下“C

hdu1171(母函数或多重背包)

题意:把物品分成两份,使得价值最接近 可以用背包,或者是母函数来解,母函数(1 + x^v+x^2v+.....+x^num*v)(1 + x^v+x^2v+.....+x^num*v)(1 + x^v+x^2v+.....+x^num*v) 其中指数为价值,每一项的数目为(该物品数+1)个 代码如下: #include<iostream>#include<algorithm>

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

hdu 1285(拓扑排序)

题意: 给各个队间的胜负关系,让排名次,名词相同按从小到大排。 解析: 拓扑排序是应用于有向无回路图(Direct Acyclic Graph,简称DAG)上的一种排序方式,对一个有向无回路图进行拓扑排序后,所有的顶点形成一个序列,对所有边(u,v),满足u 在v 的前面。该序列说明了顶点表示的事件或状态发生的整体顺序。比较经典的是在工程活动上,某些工程完成后,另一些工程才能继续,此时

poj 2976 分数规划二分贪心(部分对总体的贡献度) poj 3111

poj 2976: 题意: 在n场考试中,每场考试共有b题,答对的题目有a题。 允许去掉k场考试,求能达到的最高正确率是多少。 解析: 假设已知准确率为x,则每场考试对于准确率的贡献值为: a - b * x,将贡献值大的排序排在前面舍弃掉后k个。 然后二分x就行了。 代码: #include <iostream>#include <cstdio>#incl

poj 3104 二分答案

题意: n件湿度为num的衣服,每秒钟自己可以蒸发掉1个湿度。 然而如果使用了暖炉,每秒可以烧掉k个湿度,但不计算蒸发了。 现在问这么多的衣服,怎么烧事件最短。 解析: 二分答案咯。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <c