8003 : 증가 배열 만들기
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 2
•통과: 0
•만든사람: suakii
문제 설명
$N$개의 정수로 이루어진 배열이 주어집니다. 당신은 각 연산마다 배열의 한 원소를 1 증가시킬 수 있습니다.
배열이 비내림차순(Non-decreasing, 즉 모든 $i > 1$에 대해 $A_{i-1} \le A_i$)이 되도록 만들기 위해 필요한 최소 연산 횟수를 구하는 프로그램을 작성하십시오.
[제약 조건]
• $1 \le N \le 2 \times 10^5$
• $1 \le A_i \le 10^9$
배열이 비내림차순(Non-decreasing, 즉 모든 $i > 1$에 대해 $A_{i-1} \le A_i$)이 되도록 만들기 위해 필요한 최소 연산 횟수를 구하는 프로그램을 작성하십시오.
[제약 조건]
• $1 \le N \le 2 \times 10^5$
• $1 \le A_i \le 10^9$
입력 설명
첫째 줄에 정수 $N$이 주어집니다.
둘째 줄에 $N$개의 정수 $A_1, A_2, \ldots, A_N$이 공백으로 구분되어 주어집니다.
둘째 줄에 $N$개의 정수 $A_1, A_2, \ldots, A_N$이 공백으로 구분되어 주어집니다.
출력 설명
배열을 비내림차순으로 만들기 위한 최소 연산 횟수를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5
3 2 5 1 7
출력 예시
COPY
복사되었습니다!
복사되었습니다!
5도움
배열을 앞에서부터 순회하며 $A_i < A_{i-1}$인 경우, $A_i$를 최소한 $A_{i-1}$과 같아질 때까지 키워야 하므로 연산 횟수에 $(A_{i-1} - A_i)$를 누적하고 $A_i = A_{i-1}$로 갱신합니다.
누적 연산 횟수는 32비트 정수 범위를 초과할 수 있으므로 64비트 정수형(Python은 기본 지원)을 사용해야 합니다.
누적 연산 횟수는 32비트 정수 범위를 초과할 수 있으므로 64비트 정수형(Python은 기본 지원)을 사용해야 합니다.