Skip to Content
CTRL K

Increasing Array II

Complejidad temporal: O(Nlog⁡N)\mathcal O(N\log N)

Este problema es similar a CF 713C , salvo que debemos crear un arreglo no decreciente.

Aquí está el tutorial de zscoder .

#include <queue>
#include <stdio.h>
using namespace std;
 
int n, t;
long long ans = 0;
priority_queue<int> Q;
 
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &t);
		Q.push(t);
		ans += Q.top() - t;
		Q.pop();
		Q.push(t);
	}
	printf("%lld", ans);
	return 0;
}
from heapq import heappush, heappop
 
n = int(input())
arr = list(map(int, input().split()))
heap = []
 
ans = 0
 
for i in range(n):
	heappush(heap, -arr[i])
	if arr[i] < -heap[0]:
		ans += -heappop(heap) - arr[i]
		heappush(heap, -arr[i])
 
print(ans)
Fundamentos