51nod-Huffman 인코딩

1326 단어
질문:
한 늙은 목수는 긴 막대기를 N 토막으로 썰어야 한다.각 세그먼트의 길이는 각각 L1, L2,......,LN(1 < = L1, L2,..., LN < = 1000, 모두 정수)의 길이 단위입니다.우리는 절단할 때 정수점에서만 자르고 목재 손실은 없다고 생각한다.
목수는 매번 절단에 걸리는 체력이 이 방망이의 길이와 정비례하는 것을 발견했고, 절단 길이가 1인 방망이를 설치하면 체력 1단위를 소비하는 것도 괜찮다.예를 들어 N=3, L1=3, L2=4, L3=5라면 나무 막대기는 원래 길이가 12이고 목수는 12를 3+9.로 자르는 등 여러 가지 방법이 있다.체력 12를 소비하고 9를 4+5로 썰어 9의 체력을 소비하여 총 21의 체력을 소비한다.12를 4+8로 잘라 12, 8을 3+5로 썰어 8, 총 20의 체력을 소모할 수 있다.분명히 후자는 전자보다 체력을 더 절약한다.
그렇다면 목수는 최소한 얼마나 많은 체력을 들여야만 절단 임무를 완성할 수 있을까?
입력
 1 ：1   N(2 <= N <= 50000)
 2 - N + 1 ：  1   Li(1 <= Li <= 1000)。

출력
         。

입력 예
3
3
4
5

출력 예
19

코드는 다음과 같습니다.
#include<stdio.h>
#include<queue>
using namespace std;
priority_queue< int ,vector<int>, greater<int> >q;
int main(){
	int n,i,j;
	int L,sum;
	long long ans;
	while(scanf("%d",&n)!=EOF){
		while(!q.empty())q.pop();
		for(i=1;i<=n;i++){
			scanf("%d",&L);
			q.push(L);
			
		}
		ans=0;
		while(q.size()!=1){
			int a=q.top();
			q.pop();
			int b=q.top();
			q.pop();
		    sum=a+b;
		    ans+=sum;
		    q.push(sum);
		}
		printf("%lld
",ans);
		
	}
	return 0;
}
Programmers_Hash_위장
Spring @ Valid 의 두 가지 용법

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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