데이터 구조 - 더미 - 합병 과일

제목 설명
과일 합치 기 (fruit)
제목 은 한 과수원 에서 이미 모든 과일 을 떨 어 뜨 렸 고 과일의 종류 에 따라 서로 다른 더미 로 나 누 었 다 는 것 이다.모든 과일 을 한 무더기 로 합성 하기 로 많이 결정 하 세 요.매번 합병 할 때마다 두 무더기 의 과일 을 한데 모 을 수 있 고 소모 하 는 체력 은 두 무더기 의 과일 무게 의 합 과 같다.모든 과일 이 n - 1 차 합병 을 거 친 후에 한 무더기 만 남 았 음 을 알 수 있다.과일 을 합병 할 때 총 소모 되 는 체력 은 합병 할 때마다 소모 되 는 체력 과 같다.이 과일 들 을 집 으로 옮 기 는 데 많은 힘 을 들 여야 하기 때문에 과일 을 합 칠 때 가능 한 한 체력 을 절약해 야 한다.모든 과일의 무 게 를 1 로 가정 하고 과일의 종류 수 와 모든 과일의 수 를 알 고 있 습 니 다. 당신 의 임 무 는 합병 순서 방안 을 설계 하여 많은 체력 을 최소 화하 고 이 최소 의 체력 소모 치 를 수출 하 는 것 입 니 다.예 를 들 어 세 가지 과일 이 있 는데 그 수 는 1, 2, 9 이다.먼저 1, 2 더 미 를 합 칠 수 있 고, 새 더 미 는 3 이 며, 체력 소 모 는 3 이다.이 어 새 더 미 를 기 존의 세 번 째 더 미 를 합 쳐 새로운 더 미 를 얻 었 고, 숫자 는 12 이 며, 체력 은 12 이다.그래서 체력 을 많이 소모 한다 = 3 + 12 = 15.15 가 최소 체력 소모 치 임 을 증명 할 수 있다.
첫 번 째 줄 입력: 하나의 정수 n (1 ≤ n ≤ 10000) 은 과일의 종류 수 를 나타 낸다.두 번 째 줄: n 개의 정 수 를 포함 하고 빈 칸 으로 구분 하 며, i 번 째 정수 ai (1 ≤ ai ≤ 20000) 는 i 번 째 과일의 수량 입 니 다.
출력 한 줄 은 하나의 정수, 즉 최소 체력 소모 값 만 포함 합 니 다.입력 데 이 터 는 이 값 이 2 ^ 31 보다 작 음 을 보증 합 니 다.
샘플 입력
출력
 
 
분석
이 문 제 는 동태 적 으로 계 획 된 '합병 돌' 과 비슷 하지만 합병 돌 은 인접 한 두 무더기 만 합 칠 수 있 고 이 문 제 는 임 의 두 더 미 를 합 칠 수 있다.
전체적인 사고방식 에서 볼 때 우 리 는 먼저 수량 이 가장 적은 두 무 더 기 를 합병 해 야 한다. 먼저 정렬 을 해 야 한다. (권장 용: 정렬, 정렬 과 빠 른 정렬)
제목 에 있어 서 는 과일 이 합 쳐 질 때마다 합 쳐 진 데 이 터 를 다시 정렬 해 야 하기 때문이다.
그래서 이 문 제 는 더미 로 정렬 하면 새로운 데 이 터 를 신속하게 처리 할 수 있다.
 
 
법 1: 원 배열 에서 직접 합병 하고 합병 한 후에 뒤의 데 이 터 를 앞으로 이동 시 킨 다음 에 길 이 를 1 로 줄 이 고 빠 른 정렬 을 한다.
그러나 이런 알고리즘 은 과감하게 시간 을 초과 했다. 데이터 의 크기 가 10000 이내 이기 때문에 데 이 터 를 대량으로 이동 하고 여러 번 정렬 하면 많은 시간 을 소모 했다.
다음 코드 는 7 개의 시간 을 초과 하 였 습 니 다.
 

#include
#include
#include
using namespace std;
int a[10005],q,n,b[10005];
void put(int k)
{
 a[q++]=k;
 //push_heap(a,a+q);
 push_heap(a,a+q,greater());
}
int get()
{
 //pop_heap(a,a+w);
 pop_heap(a,a+q,greater());
 return a[--q];
}
int main()
{
 //freopen("fruit.in","r",stdin);
 //freopen("fruit.out","w",stdout);
 int i,j,x,n,sum=0;
 scanf("%d",&n);
 for(i=0;i1;){
  b[0]=b[0]+b[1];
  sum+=b[0];
  for(j=1;j

 
 
 
법 2: 더미 로 정렬 한 후 앞의 두 개의 숫자 get () 을 나 오고 더 해서 두 개의 숫자 와 put () 를 들 어가 서 한 번 더 쌓 아 유지 합 니 다.그리고
앞의 두 개의 숫자 get () 이 나 오 면... (이상 의 조작 을 반복) 이 알고리즘 은 비교적 간단 하고 복잡 도가 낮 으 며 속도 가 빠르다.(이 방법 을 사용 하 는 것 을 권장 합 니 다)

#include
#include
#include
using namespace std;
int a[10005],q,n,b[10005];
void put(int k)
{
	a[q++]=k;
	//push_heap(a,a+q);
	push_heap(a,a+q,greater());
}
int get()
{
	//pop_heap(a,a+w);
	pop_heap(a,a+q,greater());
	return a[--q];
}
int main()
{
	//freopen("fruit.in","r",stdin);
	//freopen("fruit.out","w",stdout);
	int i,x,n,sum=0;
	scanf("%d",&n);
	for(i=0;i

 
 
법 3: 우선 대기 열 에서 우선 순 위 를 이용 하여 정렬 합 니 다. 방법 은 위의 방법 과 차이 가 많 지 않 지만 속 도 는 위의 방법 보다 느 립 니 다.
우선 대기 열 은 모든 데 이 터 를 우선 순위 로 배열 해 야 하기 때문에, 쌓 기 는 최상 위 데이터 (즉 첫 번 째 데이터) 가 가장 좋 으 면 된다.
 

#include
#include
#include
using namespace std;
priority_queue,greater >h;
int main()
{
	freopen("fruit2.in","r",stdin);
	freopen("fruit2.out","w",stdout);
	int i,x,n,y,sum=0;
	scanf("%d",&n);
	for(i=0;i