UDP广播协议叫吃饭

用户名：Mustenaka

访问量：134750

签　名：

个人博客www.mustenaka.cn

等　　级
排　　名	12
经　　验	23714
参赛次数	8
文章发表	196
年　　龄	3
在职情况	学生
学　　校	Sky_box
专　　业	NE

　　自我简介：

欢迎光临我的博客www.mustenaka.cn，Python，C#，U3D，C/C++开发合作可以找我

TA的其他文章

C语言训练-计算t=1+1/2+1/3+...+1/n （C++代码）
浏览：685

C语言训练-邮票组合问题* （C++代码）其实只需要结果输出19就可以了
浏览：429

蓝桥杯算法提高VIP-删除数组中的0元素（C++代码）正经の描述
浏览：385

你可能喜欢

C语言程序设计教程（第三版）课后习题5.5 （Java代码）

P1001-题解(C++ && Python 代码)思路最重要

　　作者: UDP广播协议叫吃饭　　　　发表时间：2019-12-05 01:38:10 浏览：1271　|　评论：4　

原题链接：第K极值

### **思路重要（过后python再解答一波）**
一拿到题目，首先得到两个信息
1. 需要进行质数判断
2. 需要找到第K大的数字

根据这两点，我首先自己撸了一个函数求解质数，*最朴素的质数判断方法，就是直接从数字本身往下递减，每一个递减的数看是否与本身整除，一直到数字2结束，如果可以整除说明不是质数，不能整除说明是质数，观察题意思之后再写一个特判将负数剔除*，然后对于第K大的数字直接进行一个sort然后取值即可，结果超时WA了
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;

const int maxn=10005;
int n,k;
int arr[maxn]={0};
int ans=0;

string is_pre(int n){
	if(n<2)	return "NO";
	for(int i=n-1;i>=2;i--){
		if(n%i==0){
			return "NO";
		}
	}
	return "YES";
}

int main(){
	cin>>n>>k;
	for(int i=0;i<n;i++){
		cin>>arr[i]; 
	}
	sort(arr,arr+n);
	ans=arr[n-k]-arr[k-1];
	cout<<is_pre(ans)<<endl<<ans<<endl;
	return 0;
}
```
【当时WA掉的代码，超时28%】

那么我们知道C++ STL中的算法类sort排序底层是一个优化的快速排序，即便是快速排序在一般情况下也要达到O(nlogn)的复杂程度，而对于我们仅仅只需要求的部分数据的情况下，排序显得未免有些**浪费资源**。而正是这个资源的浪费造成了超时。

那么有什么办法可以解决这个资源浪费，刚好取得到这个第K大的数据就停止呢？

答案是有的，而且正式利用排序，而本题存在一个第K大和第K小两个数据，又恰好更加适合**二分的思想**。

略微借鉴了一点【简单选择排序】的思维进行排序查找，同时开上下两层选择进行二分，答案方法不是最优化的但却是最容易摸索到的。

> 【简单选择排序】的过程如下：
1.我们设置两个记录i和j，i自数组第一个元素开始，j自i+1个元素开始。
2.接着j遍历整个数组，选出整个数组最小的值，并让这个最小的值和i的位置交换（如果i选择的元素是最小的则不需要交换），我们称这个过程为一趟选择排序。
3.i选中下一个元素(i++)，重复进行每一趟选择排序。
4.持续上述步骤，使得i到达n-1处，即完成排序 。

我们所作的修改就是双向进行【简单选择排序】，同时顺序排（从头开始）+逆序排（从尾开始），再加入一个特殊判断，进行了K躺排序之后直接取得当时的两端排序的值进行减法操作，并返回这个值。

这样就能够极大幅度的优化排序所造成的资源浪费情况从而AC本题。
代码如下：
```cpp
#include<bits/stdc++.h>
using namespace std;

const int maxn=10005;
int n,k;
int arr[maxn]={0};
int ans=0;

string is_pre(int n){
	if(n<2)	return "NO";
	for(int i=n-1;i>=2;i--){
		if(n%i==0){
			return "NO";
		}
	}
	return "YES";
}

inline int sortSearch(int l,int r,int cnt){
	int dl=l+1,dr=r-1;
	while(dl<=r){
		if(arr[dl]<arr[l]){
			swap(arr[dl],arr[l]);
		} 
		dl++;
	}
	while(dr>=l){
		if(arr[dr]>arr[r]){
			swap(arr[dr],arr[r]);
		} 
		dr--;
	}

if(cnt==k-1){
		return arr[r]-arr[l];
	}
	sortSearch(l+1,r-1,cnt+1);
}

int main(){
	cin>>n>>k;
	for(int i=0;i<n;i++){
		cin>>arr[i]; 
	}
	//sort is O(nlogn) will Unlimit time
	//sort(arr,arr+n);		
	//ans=arr[n-k]-arr[k-1];
	ans=sortSearch(0,n-1,0);
	cout<<is_pre(ans)<<endl<<ans<<endl;
	return 0;
}
```
刚好两个函数对应两个功能。

接下来是喜闻乐见的Py时间，本人喜欢Py压缩代码行数数写（在不影响阅读和美观的前提下），看看本题目在Py下的情况如何？

```python
def is_pre(n):
    if(n<2):    return "NO"
    for i in reversed(range(2,n)):
        if(n%i==0): return "NO"
    return "YES"

def sortSearch(l,r,cnt):
    dl,dr=l+1,r-1
    while dl<=r:
        if arr[dl]<=arr[l]:   arr[dl],arr[l]=arr[l],arr[dl]
        dl=dl+1
    while dr>=l:
        if arr[dr]>=arr[r]:   arr[dr],arr[r]=arr[r],arr[dr]
        dr=dr-1
    return arr[r]-arr[l] if(cnt==k-1) else sortSearch(l+1,r-1,cnt+1)

n,k=map(int,input().split())
arr=[int(i) for i in input().split()]

ans=sortSearch(0,n-1,0)
print(is_pre(ans),ans,sep='\n')
```

嗯，很明显，它超时了。

0.0分

8 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

编程语言转换

万能编程问答

代码解释器

　　评论区

秃头大法不秃头

为什么差值会有负数呢

2021-08-21 20:05:12

北京买卖银行卡丨

可以

2020-03-30 22:42:42

RioTian

思路很清晰呢

2020-02-07 15:05:12

旺仔努力写程序

0.0

2019-12-18 15:30:26

UDP广播协议叫吃饭

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.5 （Java代码）

明明的随机数（C++代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题6.6 （C++代码）

C二级辅导-阶乘数列（C语言代码）

P1001-题解(C++ && Python 代码)思路最重要

评论区

精彩推荐

产生数（C++代码）（大数乘法也是可以避免的么hhhh）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

不容易系列2 （C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （C++代码）

【绝对值排序】（C语言代码）

三角形（C语言代码）

水仙花（C语言代码）

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

A+B for Input-Output Practice (IV) （C语言代码）

UDP广播协议叫吃饭

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.5 （Java代码）

明明的随机数 （C++代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题6.6 （C++代码）

C二级辅导-阶乘数列 （C语言代码）

P1001-题解(C++ && Python 代码)思路最重要

评论区

精彩推荐

产生数 （C++代码）（大数乘法也是可以避免的么hhhh）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

不容易系列2 （C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （C++代码）

【绝对值排序】 （C语言代码）

三角形 （C语言代码）

水仙花 （C语言代码）

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

A+B for Input-Output Practice (IV) （C语言代码）

明明的随机数（C++代码）

C二级辅导-阶乘数列（C语言代码）

　　评论区

产生数（C++代码）（大数乘法也是可以避免的么hhhh）

【绝对值排序】（C语言代码）

三角形（C语言代码）

水仙花（C语言代码）