题目描述
不使用小项堆,使用循环和指针数组完成题目,思想一样。观看闫总视频。
样例
#include <bits/stdc++.h>
using namespace std;
const int N = 2010;
int a[N],b[N],c[N];
int m,n;
void merge(){
for(int i=0;i<n;i++) c[i]=b[i]+a[0];
int help[N];
int zz[N];//指针数组,代表c[i]中是a[?],?就是z[i]中的值
memset(zz,0,sizeof(zz));
for(int i=0;i<n;i++){
int minx=INT_MAX,miny=-1;
for(int j=0;j<n;j++){
if(minx>c[j]){
minx=c[j];
miny=j;
}
}
help[i] = minx;
c[miny]=c[miny]-a[zz[miny]]+a[zz[miny]+1];
zz[miny]++;
}
for(int i=0;i<n;i++) a[i]=help[i];
}
int main()
{
int T;
cin>>T;
while(T--)
{
cin>>m>>n;
for(int i=0;i<n;i++) scanf("%d",&a[i]);
sort(a,a+n);
for(int j = 1;j<m;j++){
for(int i=0;i<n;i++){
scanf("%d",&b[i]);
}
merge();
}
for(int i=0;i<n;i++){
printf("%d",a[i]);
if(i<n-1) printf(" ");
else printf("\n");
}
}
return 0;
}
代码2
使用小项堆。简化代码
时间复杂度
参考文献
C++ 代码
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N = 2010;
typedef pair<int,int> PII;
int a[N],b[N],c[N];
int m,n;
void merge(){
priority_queue<PII,vector<PII>,greater<PII> > heap;
for(int i=0;i<n;i++) heap.push({b[i]+a[0],0});
for(int i=0;i<n;i++){
auto p = heap.top();
heap.pop();
c[i] = p.x;
heap.push({p.x-a[p.y]+a[p.y + 1],p.y+1});
}
memcpy(a,c,sizeof(a));
}
int main()
{
int T;
cin>>T;
while(T--)
{
cin>>m>>n;
for(int i=0;i<n;i++) scanf("%d",&a[i]);
sort(a,a+n);
for(int j = 1;j<m;j++){
for(int i=0;i<n;i++){
scanf("%d",&b[i]);
}
merge();
}
for(int i=0;i<n;i++){
printf("%d",a[i]);
if(i<n-1) printf(" ");
else printf("\n");
}
}
return 0;
}