UDP广播协议叫吃饭

用户名：Mustenaka

访问量：149550

签　名：

个人博客www.mustenaka.cn

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

　　自我简介：

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

TA的其他文章

工程化的C++代码实现
浏览：125

2664: 蓝桥杯2022年第十三届省赛真题-求和
浏览：680

Vector2 结构体模版 c++ 版本
浏览：55

你可能喜欢

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

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

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

　　作者: UDP广播协议叫吃饭　　　　发表时间：2019-12-05 01:38:10 浏览：1421　|　评论：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语言训练-尼科彻斯定理（C语言代码）

用筛法求之N内的素数。（C语言代码）

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

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

C二级辅导-计负均正（C语言代码）

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

评论区

精彩推荐

C语言考试练习题_保留字母（C语言代码）

C语言考试练习题_排列（C++代码）

点我有惊喜！你懂得！

2^k进制数（C++代码）使用递归方法

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

字符串的输入输出处理（C语言代码）

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

WU-格式化数据输出（C语言代码）

WU-链表数据求和操作（C++代码）

数字游戏（C++代码）

UDP广播协议叫吃饭

TA的其他文章

你可能喜欢

C语言训练-尼科彻斯定理 （C语言代码）

用筛法求之N内的素数。 （C语言代码）

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

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

C二级辅导-计负均正 （C语言代码）

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

评论区

精彩推荐

C语言考试练习题_保留字母 （C语言代码）

C语言考试练习题_排列 （C++代码）

点我有惊喜！你懂得！

2^k进制数 （C++代码）使用递归方法

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

字符串的输入输出处理 （C语言代码）

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

WU-格式化数据输出 （C语言代码）

WU-链表数据求和操作 （C++代码）

数字游戏 （C++代码）

C语言训练-尼科彻斯定理（C语言代码）

用筛法求之N内的素数。（C语言代码）

C二级辅导-计负均正（C语言代码）

　　评论区

C语言考试练习题_保留字母（C语言代码）

C语言考试练习题_排列（C++代码）

2^k进制数（C++代码）使用递归方法

字符串的输入输出处理（C语言代码）

WU-格式化数据输出（C语言代码）

WU-链表数据求和操作（C++代码）

数字游戏（C++代码）