백준(2513번) - 통학버스(Java) (그리디)

문제풀이를 위해서는 학교위치를 기준으로 왼쪽[학교위치(s) > 사는 곳(v)] 오른쪽[학교위치(s) < 사는 곳(v)] 두 분류의 우선순위 큐가 필요할 것이다.

 

이렇게 분류를 하고 나서 아이들을 데려오는 가장 좋은 방법은

1. 최대한 멀리 사는 친구[Math.max(Math.abs(s - v))]를 목표로 차를 끌고 간다.

2. 최대한 멀리 사는 친구들을 태우고 자리가 남는다면 학교로 복귀하는 길에 더 태운다.

 

이렇게 된다면 한 번의 움직임에 두 포인트에 사는 친구들을 픽업해 올 수 있다.

이 풀이방법을 위해 정렬 기준만 잘 잡아준다면 어렵지 않다.

<문제>

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

2513번: 통학버스

---

<소스코드>

import java.util.*;
import java.io.*;


public class Main
{
	static class node implements Comparable<node>
	{
		int vil;
		int man;
		
		public node(int vil, int man)
		{
			this.vil = vil;
			this.man = man;
		}
		
		public int compareTo(node n)	//마을 위치가 높은 순서대로 정렬
		{
			return n.vil - vil;
		}
	}
	
	public static void main (String[] args) throws IOException
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		int s = Integer.parseInt(st.nextToken());
		long ans = 0;
		
		PriorityQueue<node> bigger = new PriorityQueue<>();
		PriorityQueue<node> smaller = new PriorityQueue<>(Collections.reverseOrder());
		
		for(int i = 0 ; i < n ; i++)
		{
			st = new StringTokenizer(br.readLine());
			
			int v = Integer.parseInt(st.nextToken());
			int m = Integer.parseInt(st.nextToken());
			
			if(s < v) bigger.add(new node(v, m));
			else smaller.add(new node(v, m));
		}
		
		while(!bigger.isEmpty())
		{
			int dist = 0;
			int lim = k;
			
			while(!bigger.isEmpty())
			{
				node next = bigger.poll();
				
				dist = Math.max(dist, next.vil);
				
				if(lim < next.man)
				{
					int tmp = next.man - lim;
					bigger.add(new node(next.vil, tmp));
					break;
				}
				else
				{
					lim -= next.man;
				}
			}
			
			ans += ((dist-s)*2);
		}
		
		while(!smaller.isEmpty())
		{
			int dist = Integer.MAX_VALUE;
			int lim = k;
			
			while(!smaller.isEmpty())
			{
				node next = smaller.poll();
				
				dist = Math.min(dist, next.vil);
				
				if(lim < next.man)
				{
					int tmp = next.man - lim;
					smaller.add(new node(next.vil, tmp));
					break;
				}
				else
				{
					lim -= next.man;
				}
			}
			
			ans += ((s-dist)*2);
		}
		
		System.out.println(ans);
	}

}