问题 L: minval

时间限制: 3 Sec  内存限制: 256 MB
提交: 671  解决: 82
[ 提交][ 状态][ 讨论版][命题人: 外部导入]
题目链接

题目描述

有两个长度为N的序列A和B，在A和B中各任取一个数相加可以得到N2个和，求这N2个和中最小的N个。

输入

第一行输入一个正整数N（1<=N<=100000）；

第二行N个整数Ai且Ai<=109；第三行N个整数Bi且Bi<=109。

输出

输出仅一行，包含n个整数，从小到大输出这n个最小的和，相邻数字之间用空格隔开。

样例输入

51 3 2 4 56 3 4 1 7

样例输出

2 3 4 4 5

题解:第一次使用优先队列，一次尝试。

//用优先队列AC的代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 100000+5;
int a[maxn], b[maxn];
int main()
{
    int n;
    long long sum,min[maxn];
    priority_queue<long long> s;
    cin>>n;
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);  
    for(int i=1;i<=n;i++) scanf("%d",&b[i]);  
    sort(a+1,a+1+n);  
    sort(b+1,b+1+n);  
    for(int i=1;i<=n;i++)  
        s.push(a[1]+b[i]);  
    for(int i=2;i<=n;i++)
	{  
        for(int j=1;j<=n;j++)
		{  
            int num=a[i]+b[j];  
            if(s.top()<=num) break;  
            s.pop(); 
            s.push(num);  
        }  
    }
    for (int i = n - 1; i >= 0; i--)
    {
        min[i] = s.top();
        s.pop();
    }
    for (int i = 0; i < n; i++)
    {
        printf("%lld ",min[i]);
    }
    return 0;
}

//不能AC的代码

#include<bits/stdc++.h>
using namespace std;
int a[100000+5],b[100000+5],c[100000+5];
int main()
{
	//freopen ("Date.txt","r",stdin);
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
	}
	for(int i=0;i<n;i++)
	{
		scanf("%d",&b[i]);
	}
	sort(a,a+n);
	sort(b,b+n);
	for(int i=0;i<n;i++)
	{
		c[i]=a[0]+b[i];
	}
	for(int i=1;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			int sum1=a[i]+b[j];
			if(sum1>c[n-1]) break;
			c[n-1]=sum1;
			int kk=n-1;
			while(c[kk]<c[kk-1])
			{
				int tt=c[kk];
				c[kk]=c[kk-1];
				c[kk-1]=tt;
				kk--;
			}
		} 
		if(a[i]>c[n-1]) break;
	}
	for(int i=0;i<n;i++)
	{
		if(i==0)
		printf("%d",c[i]);
		else
		printf(" %d",c[i]);
	}
	printf("\n");
	return 0;
}