목장 을 수리 하 다

13284 단어 알고리즘c 언어
목장 의 울 타 리 를 수리 하려 는 농 부 는 울 타 리 를 재 어 보 니 나무 한 토막 당 길이 가 정수 L i 의 길이 단위 인 N 개의 나무 가 필요 하 다 는 것 을 알 게 되 었 다. 그래서 그 는 길 고 N 개의 나 무 를 톱질 할 수 있 는 긴 나 무 를 샀 다. 즉, 이 나무의 길 이 는 L i 의 합계 이다.
그러나 농 부 는 톱 이 없어 서 나 무 를 톱질 하 는 보수 가 이 나무의 길이 와 정비례 한다.간단하게 보 수 를 주 는 것 은 톱질 한 나무의 길이 와 같다.예 를 들 어 길이 가 20 인 나 무 를 길이 가 8, 7, 5 인 3 단 으로 톱질 하고 첫 번 째 나 무 를 톱질 하 는 데 20 을 쓰 고 나 무 를 12 와 8 로 톱질 해 야 한다.두 번 째 나 무 를 자 르 는 데 12 가 들 고 길이 가 12 인 나 무 를 7 과 5 로 자 르 면 총 32 가 든다.처음 나 무 를 15 와 5 로 톱질 하면 두 번 째 나 무 를 톱질 하 는 데 15 가 들 고 총 35 (32 이상) 가 든다.
농부 가 나 무 를 N 조각 으로 자 르 는 데 드 는 최소한 의 비용 을 계산 할 수 있 도록 프로그램 을 만들어 주세요.
입력 형식:
입력 은 먼저 정수 N (≤ 104) 을 주 고 나 무 를 N 조각 으로 톱질 하 겠 다 는 뜻 입 니 다.두 번 째 줄 은 N 개의 정수 (≤ 50) 를 제시 하여 각 토막 의 길 이 를 나타 낸다.
출력 형식:
나 무 를 N 조각 으로 톱질 하 는 데 드 는 정 수 를 출력 합 니 다.
입력 예시:
8
4 5 1 2 1 3 1 1

출력 예시:
49

    더미, 효율 적 이 고 간단 합 니 다. 쌓 는 것 이 순서 보다 빠 를 것 입 니 다. 코드 결벽 증 을 기 르 는 것 은 문 제 를 쓰 는 것 부터 시작 합 니 다. 여기 Max 는 10001, 피의 교훈 으로 설정 해 야 합 니 다. 보초병 을 사 용 했 습 니 다. 바 꾸 었 습 니 다. 뭐 가 틀 렸 는 지 모 르 겠 습 니 다. 다른 사람의 코드 를 둘 러 보 니 자신 보다 못 하 다 는 것 을 알 게 되 었 습 니 다. 30 분 동안 멍하니 보 니 Max 가 문제 가 생 겼 다. 복종 하고 한 마디 하 겠 습 니 다.하 프 만 의 템 플 릿 을 직접 옮 기 는 메모리 가 10 배 나 많 았 고 정렬 보다 훨씬 빨 랐 습 니 다. 자신의 코드 향 입 니 다. 자신 을 믿 습 니 다.
예제 코드:
#include 
#include 
#define Max 10001
#define INF -1


void BulidHeap();
void Insert(int n);
void Calculate();
int Delete();

typedef struct HeapStruct MinHeap;
struct HeapStruct{
    int Data[Max];
    int Size;
};

MinHeap H;
int Sum;

int main()
{
	BulidHeap();
	Calculate();
	printf("%d",Sum);
	
}

void BulidHeap()
{
	int N,i,n;
	H.Data[0] = INF;//  
	scanf("%d",&N);
	for(i = 1; i <= N; i++){
		scanf("%d",&n);
		Insert(n);
	}
}

void Insert(int n)
{
	int i;
	i = ++H.Size;
	for( ; H.Data[i / 2] > n; i /= 2){
		H.Data[i] = H.Data[i / 2];
	}
	H.Data[i] = n;
}

void Calculate()
{
	int a1,a2;
	while(H.Size > 1){
		a1 = Delete();
		a2 = Delete();
		Insert(a1 + a2);
		Sum = Sum + a1 + a2;
	}
}

int Delete()
{
	int parent,child,t,n;
	n = H.Data[1];
	t = H.Data[H.Size--];
	for(parent = 1; parent * 2 <= H.Size;parent = child){
		child = parent * 2;
		if(H.Data[child + 1] < H.Data[child]){
			child++;
		}
		if(t <= H.Data[child]) break;
		else{
			H.Data[parent] = H.Data[child];
		}
	}
	H.Data[parent] = t;
	return n;
}

좋은 웹페이지 즐겨찾기