【Luogu P1631】序列合并

Luogu P1631

题意很好懂，不作分析

很容易想出一个解法是求出每一个和，排序后取前n个。

当然这种做法妥妥的会MLE+TLE

我们会发现实质上这种做法的缺点在于存入了大量不需要的数据。

那么该怎么进行优化呢？

观察题目，易得下列关系
a[1]+b[1]<=a[2]+b[1]<=...<=a[n]+b[1]
a[1]+b[2]<=a[2]+b[2]<=...<=a[n]+b[2]
a[1]+b[3]<=a[2]+b[3]<=...<=a[n]+b[3]
....................................
a[1]+b[n]<=a[2]+b[n]<=...<=a[n]+b[n]

很显然第一个答案必定会是a[1]+b[1]。
那么第二个答案一定会是a[1]+b[2]吗？未必如此。
假设有这样一组数据：

n=3;
a={1,1,3}
b={3,4,13}

不难得出第一个答案会是4(a[1]+b[1])，第二个答案也是4(a[2]+b[1])。
由此看出，我们在取得一个答案后，应该将他在不等式中的下一项存入候选答案中。
对于候选答案的储存，我使用了优先队列的方式，不知道开一个数组不断排序能不能过。
代码奉上：

#include<cstdio>
#include<queue>
#include<vector>
using namespace std;
priority_queue<pair<long long,int>> que;
long long n,a[100005],b[100005],ans[200005],step[200005];
int main()
{
    scanf("%lld",&n);
    for (int i=1;i<=n;i++) scanf("%lld",&a[i]);
    for (int i=1;i<=n;i++) scanf("%lld",&b[i]);
    for (int i=1;i<=n;i++)
    {
        pair<long long,int> tmp(-a[i]-b[++step[i]],i);
        //取相反数是为了因为stl的优先队列优先级默认为从大到小。 
        que.push(tmp);
    }
    for (int i=1;i<=n;i++)
    {
        long long val=que.top().first;int  tmp=que.top().second;
        printf("%lld ",-val);
        que.pop();
        pair<long long,int> now(-a[tmp]-b[++step[tmp]],tmp);
        que.push(now);
    }
    return 0;
}

【Luogu P1631】序列合并

原文：https://www.cnblogs.com/notscience/p/11788896.html