하프 만 트 리 (우선 대기 열) 합병 과일

1423 단어 나무.쌓다~ ~ ~ ~ ~ STL 용기 ~ ~ ~ ~ ~~ ~ ~ ~ 데이터 구조 ~ ~ ~ ~ ~
Input
첫 줄 에는 데이터 그룹 수 를 나타 내 는 정수 T (T < = 50) 가 포함 되 어 있 습 니 다.각 조 의 데이터 첫 줄 은 하나의 정수 n (2 < = n < = 1000) 을 포함 하고 과일의 퇴적 수 를 나타 낸다.두 번 째 줄 은 n 개의 정수 ai (ai < = 100) 를 포함 하여 모든 과일 더미 의 과일 수 를 나타 낸다.
Output
각 조 의 데 이 터 는 한 줄 로 최소 합병 대 가 를 나타 낸다.
Sample Input 
2
4
1 2 3 4
5
3 5 2 1 4

Sample Output 
19
33

우 리 는 가끔 하 프 만 나 무 를 만 들 필요 가 없다. 최종 적 인 권한 을 가 진 경로 의 길 이 를 얻 으 면 된다. (예 를 들 어 과일 을 합병 하 는 문 제 는 최소한 의 체력 만 소모 하면 된다 는 것 이다) 우 리 는 하 프 만 의 구 조 를 파악 해 야 한다.
지금 은 n 더미 의 과일 이 있 고, i 더미 에는 ai 개의 과일 이 있다.지금 이 과일 들 을 한 무더기 로 합 쳐 야 하 는데, 매번 합병 하 는 대 가 는 두 무더기 의 총 과일 수 이다.모든 과일 을 합병 하 는 최소한 의 대 가 를 구하 다.사상 을 만 들 면 됩 니 다. 즉, 가장 작은 요 소 를 두 개 반복 해서 선택 하고 하나의 요소 만 남 을 때 까지 합병 하 는 것 입 니 다.
#include
#include 
using namespace std;

priority_queue, greater > q;

int main (){
	int T;
	scanf("%d", &T);
	while(T--){
		int n;
		long long temp, x, y, ans = 0;
		while(!q.empty()) q.pop();
		scanf("%d", &n);
		for(int i = 0; i < n; i++){
			scanf("%lld", &temp);
			q.push(temp);
		}
		while(q.size() > 1){		//               
			x = q.top();
			q.pop();
			y = q.top();
			q.pop();
			q.push(x + y);
			ans += x + y;
		}
		printf("%lld
", ans);		
	}

	return 0;
}

주석 트 리 초보
poj1821 Fence

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage