程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> uva11997(優先隊列,歸並)

uva11997(優先隊列,歸並)

編輯:關於C++

題意:

k個數組,每個數字k個值;

如果每個數組取一個值相加,那麼總共有k^k種結果,取前k小的值,輸出;

 

思路:

首先我們兩個數組,兩個數組找出前k小的和了,在加入第三個,這樣一直兩兩算;

因為兩個數組取出前k小的和了;那麼加入第三個數組後,那麼新的前k小肯定是第三個數組的值和那之前前k的值的和;

而求兩個數組,和的前k小,我們可以用優先隊列,加上一個動態規劃;

只有AB兩個數組.

那麼S = A[i] + B[j] 就可以推出A[i] +B[j + 1];

即S - B[j] +B[j +1];

具體可以看劉汝佳書裡的解析;

 

 

#include
#include
#include
#include
using namespace std;

struct point {
	int s, b;
	point(int a, int c) {
		s = a;
		b = c;
	}
	bool operator <(point a)const {
		return this->s > a.s;
	}
};

const int N = 1000;
int A[N][N];
int n;

void merge(int* A, int* B, int* C, int n) {
	priority_queue q;
	for(int i = 0; i < n; i++)
		q.push(point(A[i] + B[0], 0));
	for(int i = 0; i < n; i++) {
		point p = q.top();
		q.pop();
		C[i] = p.s;
		int b = p.b;
		if(b + 1 < n) 
			q.push(point(p.s - B[b] + B[b + 1], b + 1));
	}
}
int main() {
	while(scanf("%d",&n) == 1) {
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				scanf("%d",&A[i][j]);
			}
			sort(A[i], A[i] + n);
		}
		for(int i = 1; i < n; i++)
			merge(A[0], A[i], A[0], n);
		printf("%d",A[0][0]);
		for(int i = 1; i < n; i++) {
			printf(" %d",A[0][i]);
		}
		printf("\n");
	}
	return 0;
}


 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved