과일 [더미, 욕심]

제목.
n 더미 의 크기 가 다른 과일 더미 가 있 습 니 다. 매번 두 더 미 를 합 칠 때마다 두 더미 의 무 게 를 소모 합 니 다. 그것들 을 모두 합 친 최소 소 모 를 구 합 니 다.
입력
입력 은 두 줄 을 포함 하고 첫 번 째 줄 은 정수 n (1) 입 니 다.
출력
출력 은 한 줄 을 포함 합 니 다. 이 줄 은 하나의 정수 만 포함 합 니 다. 즉, 최소 체력 소모 값 입 니 다. 데 이 터 를 입력 하면 이 값 이 2 ^ 31 보다 작 습 니 다.
샘플 입력
3 1 2 9
샘플 출력
15
문제 풀이 의 사고 방향.
욕심 은 매번 가장 작은 두 개 를 합 치 는 것 이다. 여 기 는 쌓 는 것 이 편리 하 다.
코드

#include
using namespace std;
int a[10001],num,x,n;
long long s,u;
void up(int x)
{
    int t;
    while (x>1 && a[x]2])
{
t=a[x];a[x]=a[x/2];a[x/2]=t;
x/=2;
}
} / / 로 더 를 조정 합 니 다.
void down(int x)
{
int t,y;
while (x*2<=num && a[x]>a[x*2] || x*2+1<=num && a[x]>a[x*2+1])
{
y=x*2;
if (x*2+1<=num && a[x*2]>a[x*2+1]) y++;
t=a[x];a[x]=a[y];a[y]=t;
x=y;
}
} / / 로 더 를 조정 합 니 다.
void insert(int x)
{a [+ num] = x; up (num);} / / 요소 삽입
int main()
{
scanf("%d",&n); 
for (int i=1;i<=n;i++)
{
scanf("%d",&x);
insert(x);
} / / 쌓 기
while (num>1)
{
u=a[1];a[1]=a[num];num--;down(1);
u + = a [1]; a [1] = a [num]; num -; down (1); / / 두 개의 가장 작은 것 을 취하 다
s + = u; num + +; a [num] = u; up (num); / / 합병 후 되 돌려 놓 기
}
printf("%d",s);
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

HPU - ACM 여름 훈련 2 주차 14 급 개인전: Problem D [욕심]

Problem D Problem Description 그 러 고 보 니 해동 그룹 이 안팎 으로 어려움 을 겪 고 있 고 회사 의 원로 도 XHD 부부 만 남 았 다 고 한다.분명히 여러 해 동안 싸 운 상인 으로서...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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