题解 P1392 【取数】
介绍一道基本版题目序列合并
仔细分析有何不同？
-
这里有N个数组，而上题只有两个
-
上题是求最小的N个，而这里是求其中的K个
注意到K<=M
那么
我们可以用一个数组记录前i个数组的最优K个值
并不断地与第i+1数组进行比较从而更新这K个数
从而将问题转化为序列合并去完成
那么 如何求取2个数组之间的最优K项呢？
- 对此两个数组排序
假设堆中元素不足K个，直接入大根堆。
假设堆中元素已有K个
-
A[i]+B[j]<堆顶，堆顶出堆A[i]+B[j]入堆。
-
A[i]+B[j]>=堆顶，我不仅不要此元素，由于B数组单调递增，我也不要B数组在A[i]情况下的任意解。（代码实现用BREAK）
代码时间复杂度（最大次数）：66334603（这不是电话号码）
据说计算机一秒内最多可以计算八千万次。
酱紫已有就可以以较慢的速度AC了（4089ms）
安利一下某不知名优化！
#pragma GCC optimize(5)结果：（2546ms）
上代码
手写堆，勿嫌弃
#pragma GCC optimize(5)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const long long INF=1e17;
int Num2,m,n,k,Map[805][805],b[8000];
int Ans[805];
void AddHeap(int x)
{
int Now=++Num2;b[Num2]=x;
while(Now>1&&b[Now]>b[Now/2])
{
swap(b[Now],b[Now/2]);Now/=2;
}
}
void Delete()
{
int Now=1,k;b[1]=b[Num2];Num2--;
while(Now*2<=Num2)
{
if(b[Now*2]>b[Now*2+1]||Num2==2*Now)k=Now*2;else k=Now*2+1;
if(b[Now]<b[k]){swap(b[Now],b[k]);Now=k;}else break;
}
}
void DFS(int D)
{
if(D==n+1)return;
for(int i=1;i<=k;i++)
{
for(int j=1;j<=k;j++)
{
int x=Map[1][i]+Map[D][j];
if(Num2<k)AddHeap(x);
else
{
if(b[1]>x){Delete();AddHeap(x);}
else break;
}
}
}
for(int i=k;i>=1;i--)Map[1][i]=b[1],Delete();
DFS(D+1);
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
int A[805];
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)scanf("%d",&A[j]);sort(A+1,A+1+m);
for(int j=1;j<=m;j++)Map[i][j]=A[j];
}
DFS(2);
for(int i=1;i<=k;i++)printf("%d ",Map[1][i]);puts("");
return 0;
}