13323번
👍 문제
수열 A1, A2 .. AN 이 주어진다.
B1 < B2 < ... < BN 을 만족하면서, |B1 - A1| + |B2 - A2| ... |BN - AN| 을 최소화하는 수열 B가 존재할 때, 당신은 그러한 값의 가능한 최솟값을 출력해야 한다.
수열 A와 B는 정수로만 이루어진 수열이고, 수열 B의 원소는 32비트 정수형 범위 안에 들어있어야 한다.
👍 입/출력
입력 : 첫 번째 줄에 N이 주어진다. (N ≤ 1,000,000) 두 번째 줄에 수열 A의 원소가 순서대로 주어진다. (0 ≤ Ai ≤ 2 × 109)
출력 : 가능한 |B1 - A1| + |B2 - A2| ... |BN - AN| 값의 최소를 출력한다.
👍 내 마음대로 해설
문제가 분명 짧은데 엄청 어려워서 다른 분이 했던 풀이를 참고하고 풀었었다.
거의 코드가 이 분 것을 빼다 박아버렸기에 출처를 달아놓겠다.코딩은 아래 페이지를 참고하였다. 감사합니다..
일단, 코딩을 살펴보면 priority queue에 Ai 값을 넣어주는데
Ai 값은 지금까지 priority queue에 들어간 숫자들 개수인 i-1개를 빼주어 넣어준다.
그리고 해당 우선순위 queue 안의 제일 큰 숫자(top)이 (Ai-(i-1))보다 크다면 그 값의 차이만큼 빼주고 제일 큰 숫자인 top은 해당 컨테이너에서 제거(pop)시켜주고 Ai값을 또 넣어준다.
코딩은 이해가 가는데 풀이가 따로 없어
왜 이렇게하면 최소 값이 나오는지를 엄청나게 고민했다.
직관적으로 이해해볼라 했으나 전혀 되지 않아 인터넷을 뒤져보니
slope trick이라는 놈이었다. 코드 포스나 다른 자료들을 뒤져본 결과 꽤 오래걸렸지만 결국 이해했다.
내가 정리한 slope trick 설명 : https://velog.io/@idwooin/Slope-Trick
👍 c++ 정답 코드
#include <iostream>
#include <queue>
using namespace std;
int main() {
int n;
int num;
long long result (0);
priority_queue<int> pq;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> num;
num -= i;
if (!pq.empty() && pq.top() > num){
pq.push(num); // 꼭 넣어줘야함
result+=pq.top()-num;
pq.pop();
pq.push(num);
}
else{
pq.push(num);
}
}
cout << result << '\n';
return 0;
}