《输出前k大的数》提交运行超时、答案错误
  • 板块学术版
  • 楼主魏老师
  • 当前回复17
  • 已保存回复17
  • 发布时间2023/11/26 16:56
  • 上次更新2023/11/26 19:08:06
查看原帖
《输出前k大的数》提交运行超时、答案错误
285961
魏老师楼主2023/11/26 16:56

运行超时还可以理解,优化也也知道,左边的一些数不需要继续递归,但是不知道怎么写,答案错误不能理解,我觉得我写得挺对的啊,本身又不难,请指教,谢谢

【题目描述】 给定一个数组,统计前k大的数并且把这k个数从大到小输出。

【输入】 第一行包含一个整数n,表示数组的大小。n < 100000。

第二行包含n个整数,表示数组的元素,整数之间以一个空格分开。每个整数的绝对值不超过100000000。

第三行包含一个整数k,k < n。

【输出】 从大到小输出前k大的数,每个数一行。

【输入样例】 10 4 5 6 9 8 7 1 2 3 0 5 【输出样例】 9 8 7 6 5

//输出前k大的数 
#include<bits/stdc++.h>
using namespace std;
int n,i,j,a[100010];
void binary_Search(int l,int r);
int main()
{
	cin>>j;
	for(int o=1;o<=j;o++) cin>>a[o];
	cin>>i; 
	 
	binary_Search(1,j);
	for(int o=j;o>=j-i+1;o--)
	{
		cout<<a[o]<<endl;
	}
	return 0;
}

void binary_Search(int l,int r)
{  
    int k=l,q=r,s;
    s=(l+r)/2;
    while(k<=q)
    {
    	while(a[k]<a[s]) k++;
    	while(a[q]>a[s]) q--;
    	if(k<=q)
    	{
    		swap(a[k],a[q]); 
    		k++; q--;
		}
	}
    if(l<q) binary_Search(l,q);
	if(r>k) binary_Search(k,r);
}
2023/11/26 16:56
加载中...