11997 - K Smallest Sums(优先队列)

11997 - K Smallest Sums

You’re given k arrays, each array has k integers. There are k
k ways to pick exactly one element in each
array and calculate the sum of the integers. Your task is to find the k smallest sums among them.
Input
There will be several test cases. The first line of each case contains an integer k (2 ≤ k ≤ 750). Each of
the following k lines contains k positive integers in each array. Each of these integers does not exceed
1,000,000. The input is terminated by end-of-file (EOF).
Output
For each test case, print the k smallest sums, in ascending order.
Sample Input
3
1 8 5
9 2 5
10 7 6
2
1 1
1 2
Sample Output
9 10 12
2 2

题意：

给你k个数组，从每个数组里面取个数字，求和，让找k个最小值；

大神的优先队列，自己用好友的思路写了一遍，没考虑周全，wa了，然后借助大神的思路写了一遍就对了，大神是把复杂问题简单化，把k维转化为二维；

代码：

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<queue>

#include<algorithm>

#include<vector>

using namespace std;

const int INF=0x3f3f3f3f;

const int MAXN=800;

typedef long long LL;

int mp[MAXN][MAXN];

struct Node{

	int s,p;

	Node(int s,int p):s(s),p(p){}

	friend bool operator <(Node a,Node b){

		return a.s>b.s;

	}

};

void merge(int *a,int *b,int *c,int n){

	sort(a,a+n);sort(b,b+n);

	priority_queue<Node>dl;

	for(int i=0;i<n;i++)dl.push(Node(a[i]+b[0],0));

	for(int i=0;i<n;i++){

		Node d=dl.top();dl.pop();

		c[i]=d.s;

		dl.push(Node(d.s-b[d.p]+b[d.p+1],d.p+1));

	}

}

int main(){

	int k;

	while(~scanf("%d",&k)){

				for(int i=0;i<k;i++)for(int j=0;j<k;j++)scanf("%d",&mp[i][j]);

				for(int i=1;i<k;i++){

					merge(mp[0],mp[i],mp[0],k);

				}

				for(int i=0;i<k;i++){

					if(i)printf(" ");

					printf("%d",mp[0][i]);

				}

				puts("");

			}

	return 0;}

　刚开始没考虑周全的代码：

1 2 5 100

1 2 8 100

1 8 9 100

1 10 15 100

这组数据就没过。。

wa代码：

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<queue>

#include<algorithm>

#include<vector>

using namespace std;

const int INF=0x3f3f3f3f;

const int MAXN=800;

typedef long long LL;

priority_queue<int,vector<int>,greater<int> >dl,q;

int main(){

	int k;

	while(~scanf("%d",&k)){

		while(!dl.empty())dl.pop();

		while(!q.empty())q.pop();

		int ans=0;

		int x,a,b;

	for(int i=0;i<k;i++){

	for(int j=0;j<k;j++){

			scanf("%d",&x);dl.push(x);

			}

			a=dl.top();

			ans+=a;

			dl.pop();

			b=dl.top();

			q.push(b-a);

		//	printf("%d %d\n",a,b);

			while(!dl.empty())dl.pop();

		}

		for(int i=0;i<k;i++){

			if(i)printf(" ");

			if(!i)printf("%d",ans);

			else printf("%d",ans+q.top()),q.pop();

		}

		puts("");

	}

	return 0;

}

巴特西

11997 - K Smallest Sums(优先队列)

11997 - K Smallest Sums

最新文章

热门文章