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

1582 阅读 5 评论 0 点赞

原题链接：第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分

5 人评分

本文分类：题解列表
浏览次数：1582 次浏览
发布日期：2019-12-05 01:38:10
本文链接：https://blog.dotcpp.com/a/63508

上一篇 > [搞比利]克鲁斯卡尔算法2050题-55.战争通讯-题解(C++代码)
下一篇 > 蓝桥杯算法提高VIP-队列操作-题解(C语言代码)

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

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

评论列表共有 5 条评论

发表评论取消回复

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

数位dp#2491: 信息学奥赛一本通T1587-Windy 数(C++)

点进来你会后悔的

简简单单的循环

简单的回文数

评论列表 共有 5 条评论

发表评论 取消回复

评论列表共有 5 条评论

发表评论取消回复