링크

도서관-1461

문제

세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책들의 원래 위치가 주어질 때, 책을 모두 제자리에 놔둘 때 드는 최소 걸음 수를 계산하는 프로그램을 작성하시오. 세준이는 한 걸음에 좌표 1칸씩 가며, 책의 원래 위치는 정수 좌표이다. 책을 모두 제자리에 놔둔 후에는 다시 0으로 돌아올 필요는 없다. 그리고 세준이는 한 번에 최대 M권의 책을 들 수 있다.

입력

첫째 줄에 책의 개수 N과, 세준이가 한 번에 들 수 있는 책의 개수 M이 주어진다. 둘째 줄에는 책의 위치가 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 책의 위치는 0이 아니며, 절댓값은 10,000보다 작거나 같은 정수이다.

출력

첫째 줄에 정답을 출력한다.

풀이

plus 우선순위 큐 , minus 우선순위 큐를 나눠준다.
다음 plus와 minus큐를 내림차순으로 정렬해주며 max를 저장해둔다. 그 이유는 마지막 책은 원래 위치에 가져다놓고 다시 원점으로 돌아올 필요가 없기에 마지막에 result값에 -max를 빼주면 되기 때문이다.

Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class practice {
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(br.readLine());
		int result=0;
		int n=Integer.parseInt(st.nextToken());
		int m=Integer.parseInt(st.nextToken());
		
		//두 우선순위 큐는 내림차순 정렬
		PriorityQueue<Integer> plus=new PriorityQueue<Integer>((o1,o2) -> o2-o1);
		PriorityQueue<Integer> minus=new PriorityQueue<Integer>((o1,o2) -> o2-o1);
		
		StringTokenizer st1=new StringTokenizer(br.readLine());
		for(int i=0; i<n; i++)
		{
			int num=Integer.parseInt(st1.nextToken());
			if(num>=1)
				plus.add(num);
			else
				minus.add(Math.abs(num));
		}

		//가장 멀리 있는 책의 위치를 저장
		int max=0;
		if(plus.isEmpty())
			max=minus.peek();
		else if(minus.isEmpty())
			max=plus.peek();
		else
			max=Math.max(plus.peek(), minus.peek());
		
		while(!plus.isEmpty())
		{
			int temp=plus.poll();
			for(int i=0; i<m-1; i++)
			{
				plus.poll();
				
				if(plus.isEmpty())
					break;
			}
			result+=temp*2;
		}
		
		while(!minus.isEmpty())
		{
			int temp=minus.poll();
			
			for(int i=0; i<m-1; i++)
			{
				minus.poll();
				
				if(minus.isEmpty())
					break;
			}
			result+=temp*2;
		}
		
		System.out.println(result-max);
	}
}