给定m个长度为n的序列 每个序列选一个数求和,求最小的n个

用堆来模拟搜索的过程 关键在于状态不重复
朴素写法: 用map来维护m个指针,判重
但是空间复杂度是\(mn^2\)的会爆

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;

const int N=2010;

int read()
{
	int x=0,f=0,c=getchar();
	while(c<'0'||c>'9'){if(c=='-') f=1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return f?-x:x;
}

int a[N][N];
int n,m,T;
struct Node
{
	int sum;
	int pos[N];
};
bool operator<( const Node &a,const Node &b)
{
	if(a.sum!=b.sum) return a.sum>b.sum;
	for(int i=1;i<=m;i++) 
		if(a.pos[i]!=b.pos[i])  return a.pos[i]<b.pos[i];
	return 0;
}
priority_queue< Node > q;
map<Node,bool> mp;


int main()
{
	T=read();
	loop:
	while(T--)
	{
		m=read(); n=read();
		while(q.size()) q.pop();
		mp.clear();
		for(int i=1;i<=m;i++)
		{
			for(int j=1;j<=n;j++) a[i][j]=read();
			sort(a[i]+1,a[i]+n+1);
		}
		Node tmp;tmp.sum=0; 
		for(int i=1;i<=m;i++) tmp.sum+=a[i][1];
		fill(tmp.pos+1,tmp.pos+m+1,1);
		q.push(tmp); int tot=0; mp[tmp]=1;

		while(q.size())
		{
			Node t=q.top(); q.pop();
			tot++; printf("%d ",t.sum);
			if(tot==n) {puts(""); goto loop;}
			for(int i=1;i<=m;i++)
				if(t.pos[i]<n) 
				{
					Node now=t;
					now.sum+=a[i][t.pos[i]+1]-a[i][t.pos[i]];
					now.pos[i]++;
					if(!mp[now]) 
						q.push(now),mp[now]=1;
				}
		}
		
	}
}
注意: 
在重载运算符的时候 最后要return false 否则map不能正常运行

优化:
我们按照一定的顺序来移动指针 只有移动上面的之后才能移动下面的 这样的话只需要维护最后一个指针即可
但是由于时效性 要给m个序列先排序

include

include

include

include

include

using namespace std;
const int N=2e3+10;

int read()
{
int x=0,f=0,c=getchar();
while(c<'0'||c>'9'){if(c=='-') f=1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return f?-x:x;
}

struct Node
{
int val,x,y;
bool p;
};
bool operator<(const Node &a,const Node &b){ return a.val>b.val;}
int m,n,a[N][N],p[N];
priority_queue q;

bool cmp(int x,int y){ return a[x][2]-a[x][1]<a[y][2]-a[y][1];}

int main()
{
int T=read();
while(T--)
{
while(q.size()) q.pop();
int sum=0,tot=0;
m=read(); n=read();
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++) a[i][j]=read();
sort(a[i]+1,a[i]+n+1); p[i]=i;
sum+=a[i][1];
}
sort(p+1,p+m+1,cmp);

	q.push((Node){sum,1,1,0});
	while(q.size()&&tot<n)
	{
		Node t=q.top(); q.pop();
		printf("%d ",t.val); tot++;
		int x=t.x,y=t.y;
		if(y<n) q.push( (Node){t.val+a[p[x]][y+1]-a[p[x]][y],x,y+1,0 } );
		if(x<m) 
		{
			q.push( (Node){t.val+a[p[x+1]][2]-a[p[x+1]][1],x+1,2,1} );
			if(t.p) q.push( (Node){t.val-(a[p[x]][2]-a[p[x]][1])+(a[p[x+1]][2]-a[p[x+1]][1]),x+1,2,1}  );
		}
		
	}
	puts("");
}
return 0;

}
```