목장 을 수리 하 다
그러나 농 부 는 톱 이 없어 서 나 무 를 톱질 하 는 보수 가 이 나무의 길이 와 정비례 한다.간단하게 보 수 를 주 는 것 은 톱질 한 나무의 길이 와 같다.예 를 들 어 길이 가 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;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.