도서관 C++ - 백준 1461

https://www.acmicpc.net/problem/1461

그리디 문제.

문제 접근

이 문제의 핵심적인 그리디 해법은 가까운 지점부터 간다는 것이다.

먼 지점부터 가게 되면 남은 책들이 남아있을때 가까운 지점을 먼저 가는 경우보다

더 많이 걸어야하기 때문이다.

그리고 좌표가 음수인 부분을 먼저 탐색하는 것과 나중에 탐색하는 것 중 최솟값을

출력했다.

코드는 다음과 같다.

#include <bits/stdc++.h>
using namespace std;

int n,m,inn;
priority_queue<int, vector<int>, greater<int>> ppq;
priority_queue<int, vector<int>, greater<int>> npq;

int solve(priority_queue<int, vector<int>, greater<int>> ppq, priority_queue<int, vector<int>, greater<int>> npq){
    int cnt,ans=0;
    if(ppq.size()%m!=0){
        cnt=ppq.size()%m;
        for(int i=1;i<cnt;i++) ppq.pop();
        if(ppq.size()==1 && npq.empty()) ans+=ppq.top();
        else ans+=2*ppq.top();
        ppq.pop();
    }
    while(!ppq.empty()){
        for(int i=1;i<m;i++) ppq.pop();
        if(ppq.size()==1 && npq.empty()) ans+=ppq.top();
        else ans+=2*ppq.top();
        ppq.pop();
    }
    if(npq.size()%m!=0){
        cnt=npq.size()%m;
        for(int i=1;i<cnt;i++) npq.pop();
        if(npq.size()==1) ans+=npq.top();
        else ans+=2*npq.top();
        npq.pop();
    }
    while(!npq.empty()){
        for(int i=1;i<m;i++) npq.pop();
        if(npq.size()==1) ans+=npq.top();
        else ans+=2*npq.top();
        npq.pop();
    }
    return ans;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m;
    for(int i=0;i<n;i++){
        cin >> inn;
        if(inn>0) ppq.push(inn);
        else npq.push(-inn);
    }
    cout << min(solve(ppq,npq),solve(npq,ppq));
    return 0;
}