内存有限情况下如何求前m小的数
题目背景
EXCEEDED WARNING
题目描述
有这样一些数据，它们均为小于10的9次方的正整数，且个数为n，现在请你输出其中最小的m个数。
小心溢出
Memory Limit=4000KiB
输入输出格式
输入格式：第一行以半角空格间隔开的两个正整数： n, m
接下来的n行，随机产生的n个数，保证32位整型变量可以存下。
输出格式：共m行，即题目描述中的m个数，从小到大依次输出。
内存不能装下整个数组，因此可以一次处理一半（或1/X）的数据，先获取前n/2(n/X)的m个最小值，再获取后n/2的m个最小值，这2m个值合并在一起后，再求前m个最小值。
#include <iostream>
#include <iomanip>
#include <math.h>
#include <string>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
int a[500001],b[100001];
int main()
{
int i,j,n,m,q;
cin>>n>>m;
if(n<m*2) /**< q的作用处理n小于2m的情况 */
{
q=n/2;
}
else
{
q=m;
}
for(i=1; i<=n/2; i++)
{
cin>>a[i];
}
sort(a+1,a+n/2+1);
for(i=1; i<=q; i++)
{
b[i]=a[i];
}
for(i=1; i<=n-n/2; i++)
{
cin>>a[i];
}
sort(a+1,a+n-n/2+1);
for(i=1+q; i<=q*2; i++)
{
a[i]=b[i-q];
}
sort(a+1,a+2*q+1);
for(i=1; i<=m; i++)
{
cout<<a[i]<<endl;
}
return 0;
}
查看7道真题和解析
