質問する

住宅難を解決するために、直線道路に沿っていくつかの団地が建てられた.また、この団地の住民のために、道路の1つの場所に学校が新設された.マンション団地は遠いので、スクールバスとスクールバスしか乗れないに違いない.
各マンション団地と学校の位置は道路上の座標で与えられ、各マンション団地にはここに住む学生の数がある.スクールバスは朝学校を出発し、各団地の学生を乗せて帰校する.このスクールバスは定員を超えて学生を乗せることができず、すべての学生が学校に行くまでこの過程を繰り返します.

以上のルールに従って、すべての学生を学校に行かせる例です.マンション団地A、B、Cはそれぞれ座標0、2、5カ所、団地に住む学生はそれぞれ1、2、1名である.2つのポイント間の距離は、2つのポイント座標の差として定義されます.せいぜい4人乗りのスクールバスで座標4の学校を出発して、すべての学生を学校に行かせる時、バスはまずBに行って2人乗り、Aに行って1人乗ってから学校に戻って、距離2+2+4=8を移動します.更に学校から団地Cに移動して、一人を乗せて帰ってきて、移動距離は1+1=2で、総移動距離は8+2=10です.
学校の位置、マンションごとの位置、学生数、スクールバスの定員が与えられる場合は、すべての学生が学校に通うために必要なスクールバスの総移動距離の最大値を計算するプログラムを作成してください.

入力

1行目には3つの正の整数N,K,Sがスペースを隔てて順次与えられる.最初の整数Nはマンション団地の数であり、2≦N≦30000である.2番目の整数Kは1≦K≦2000で、通学バスの定員です.3番目の整数Sは学校の位置を表す.2行目からN+1行目の間には、各マンション団地の位置と、その団地の学生数を表す整数がある.学校と団地の座標は0以上100000以下で、これらの座標はすべて異なっています.各マンションの生徒数は1以上2000以下である.

しゅつりょく

1行目に与えられた入力では、走行バスの最小移動距離が出力される.最小移動距離は10000000を超えない.

I/O例

入力

に答える

グレースケールアルゴリズムの問題
1.位置によってセルを並べ替える
2.学校の標準の左側の団地のすべての学生の学校に行く距離を求めます
3.学校の標準の右側の団地のすべての学生の学校に行く距離を求めます

コード#コード#

package _0419;
import java.io.*;
import java.util.*;
public class Main_B2513 {
	//단지의 위치와 학생 수를 저장할 클래스
	static class Point implements Comparable<Point>{
		int pos,cnt;
		Point(int pos,int cnt){
			this.pos=pos;
			this.cnt=cnt;
		}
		//위치 기준 오름차순 정렬
		@Override
		public int compareTo(Point o) {
			return this.pos-o.pos;
		}
	}
	//입력값 버스 정원, 학교 위치
	static int K,S;
	//아파트 단지 저장 배열
	static Point[]arr;
	//탐색 메서드(시작지점, 탐색해야 되는 단지 수, 탐색이 왼쪽이면 true/오른쪽이면 false)
	static int search(int start,int target,boolean left) {
		//남은 좌석, 현재 위치, 거리 합, 현재 단지까지의 거리, 학생을 등교시킨 단지 수
		int seat=K,cur=start,ans=0,dist=0,finish=0;
		//탐색해야할 단지를 모두 탐색할 때까지
		while(finish<target) {
			//남은 좌석이 없는 경우
			if(seat==0) {
				//학교 왕복 거리 더해줌
				ans+=(dist*2);
				//남은 좌석 K로 초기화
				seat=K;
				//거리 초기화
				dist=0;
			}
			//현재 단지에 있는 학생이 모두 앉을 수 있는 경우
			if(arr[cur].cnt<=seat) {
				//남은 좌석에서 현재 단지의 학생 수를 빼줌
				seat-=arr[cur].cnt;
				//거리 갱신
				dist=Math.max(dist, Math.abs(S-arr[cur].pos));
			}
			//현재 단지에 있는 학생이 모두 앉을 수 없는 경우
			else {
				//거리 갱신
				dist=Math.max(dist,Math.abs(S-arr[cur].pos));
				//현재 단지 학생을 남은 좌석에 앉힐 수 있는 만큼 앉힘
				arr[cur].cnt-=seat;
				//왕복거리 더해줌
				ans+=(dist*2);
				//거리 갱신
				dist=Math.abs(S-arr[cur].pos);
				//현재 단지의 학생을 모두 태우기 위해 몫만큼 왕복
				int div=arr[cur].cnt/K;
				//div번 왕복하고 남은 학생 수
				int mod=arr[cur].cnt%K;
				ans+=(dist*div*2);
				//학생이 남지 않았은 경우
				if(mod==0) {
					dist=0;
					seat=K;
				}
				//남은 경우
				else {
					seat=K-mod;
				}
			}
			//왼쪽 탐색
			if(left)cur++;
			//오른쪽 탐색 
			else cur--;
			//모든 학생을 태운 단지 수 +1
			finish++;
		}
		//버스에 남은 학생이 있는 경우 dist에 0이 아닌 값이 있으므로 누적 합에 더해줌
		ans+=(dist*2);
		return ans;
	}
	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()),left=0;
		K=Integer.parseInt(st.nextToken());
		S=Integer.parseInt(st.nextToken());
		arr=new Point[N];
		for(int i=0;i<N;i++) {
			st=new StringTokenizer(br.readLine());
			int pos=Integer.parseInt(st.nextToken());
			int cnt=Integer.parseInt(st.nextToken());
			arr[i]=new Point(pos,cnt);
			if(pos<S)left++;
		}
		Arrays.sort(arr);
		//왼쪽, 오른쪽 이동 거리를 더해준 것이 정답
		System.out.println(search(0, left,true)+search(N-1, N-left,false));
	}
}