题目描述
题目你们都懂的
写题解只是想回顾一下自己错在哪里了 提醒自己不要在犯错了 (菜是原罪)
1.就算是ans数组也要初始化一下啊啊 防止只有一组数据的发生
2.每次队列都要清空 因为是重新计算了 每次都是这样 qaq
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e3+10;
int n,m;
int mp[maxn][maxn];
struct node {
int i;
int j;
bool last;
int val;
};
bool operator < (node x, node y) // val优先的优先队列
{
return x.val>y.val;
}
priority_queue<node> q;
int now[maxn],ans[maxn];
int main()
{
int t;
cin>>t;
while(t--)
{
while(!q.empty()) q.pop();
int n,m;
cin>>n>>m;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
cin>>mp[i][j];
}
}
sort(mp[1]+1,mp[1]+m+1);
//if(n>=2) sort(mp[2]+1,mp[2]+m+1);
for(int i = 1; i <= m; i++) now[i] = mp[1][i]; // 这个是我们的比较数组
for(int i = 1; i <= m; i++) ans[i] = mp[1][i]; // 就算是ans数组也要初始化一下啊啊
for(int i = 2; i <= n; i++)
{
while(!q.empty()) q.pop();
sort(mp[i]+1,mp[i]+m+1);
q.push(node{1,1,false,now[1]+mp[i][1]});
int temp = 1;
while(temp<=m)
{
node f = q.top();
q.pop();
ans[temp] = f.val;
q.push(node{f.i,f.j+1,true,now[f.i]+mp[i][f.j+1]});
if(f.last==false)
q.push(node{f.i+1,f.j,false,mp[i][f.j] + now[f.i+1]});
temp++;
}
for(int i = 1; i <= m; i++) now[i] = ans[i];
}
for(int i = 1; i <= m; i++) cout<<ans[i]<<" ";
cout<<endl;
}
}
总感觉二维数组浪费内存了(不是杠精)