CSES 2. Sliding Cost (1077)

출처: https://cses.fi/problemset/task/1077

---

문제 설명

You are given an array of n integers. Your task is to calculate for each window of k elements, from left to right, the minimum total cost of making all elements equal.

You can increase or decrease each element with cost x where x is the difference between the new and the original value. The total cost is the sum of such costs.

입력 

The first input line contains two integers n and k: the number of elements and the size of the window.

Then there are n integers x_1,x_2,…,x_n: the contents of the array.

출력  

Output n−k+1 values: the costs.

입력 예

8 3
2 4 3 5 8 1 2 1

출력 예

2 2 5 7 7 1

제약조건

• 1 <= k  <= n <= 2x10^5
• 1 <= x_i <= 10^9

---

문제 풀이 내용

중간값을 출력하는 문제의 확장이다. 다만, 이경우에 윈도우를 움직일때마다 새롭게 변경되는 중간값과 그것을 기준으로 하는 비용을 다시 계산하면, 시간제한에 걸린다. 

바로 직전의 중간값과 비용을 저장하고 있다가, 새로 변경되는 부분만큼만 비용을 갱신하는 방법을 사용한다.

프로그램 내용

...
    vector<long> num_arr(tN + 1);

    for (int id = 1; id <= tN; ++id)
        cin >> num_arr[id];

	long cost = 0;
    long old_med = 0;
    long med = 0;

    if (tK == 1) 
        for (int id = 1; id <= tN; ++id)
            cout << 0 << " ";
    else
        priority_queue<pair<int, int>, vector<pair<int, int>>, less<pair<int, int>>> lpq;
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> rpq;

        long mid = (tK + 1) / 2;
        int w_size = 0;
        for (int id = 1; id <= tN ; ++id) 
            while (!lpq.empty() && lpq.top().second <= id - tK) lpq.pop();
            while (!rpq.empty() && rpq.top().second <= id - tK) rpq.pop();

            if (w_size < mid) 
                rpq.push(make_pair(num_arr[id], id));
                auto tmp = rpq.top();
                rpq.pop();
                lpq.push(tmp);
                ++w_size;
            else 
                lpq.push(make_pair(num_arr[id], id));
                auto tmp = lpq.top();
                lpq.pop();
                rpq.push(tmp);

            while (!lpq.empty() && lpq.top().second <= id - tK) lpq.pop();
            while (!rpq.empty() && rpq.top().second <= id - tK) rpq.pop();

            if (id == tK) 
                old_med = lpq.top().first;
                for (int idn = 1; idn <= tK; ++idn) 
                    cost += abs(num_arr[idn] - old_med);
            else if (id > tK)  
                med = lpq.top().first;

                cost = cost + abs(med - num_arr[id]) - abs(old_med - num_arr[id - tK]);

                if (tK % 2 == 0) cost -= (med - old_med);

                old_med = med;
            else 
                continue;
            if (num_arr[id - tK + 1] <= lpq.top().first) --w_size;
...

 

Sorting and Searching ( link )