結果

問題 No.370 道路の掃除
ユーザー uafr_cs
提出日時 2017-10-29 22:23:07
言語 Java
(openjdk 23)
結果
AC  
実行時間 68 ms / 2,000 ms
コード長 2,508 bytes
コンパイル時間 2,188 ms
コンパイル使用メモリ 79,224 KB
実行使用メモリ 37,888 KB
最終ジャッジ日時 2024-11-22 05:40:16
合計ジャッジ時間 5,253 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.io.BufferedReader;
import java.io.Closeable;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class Main {
	
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		
		final int N = sc.nextInt();
		final int M = sc.nextInt();
		
		int plus = 0, minus = 0;
		int[] pos = new int[M];
		for(int i = 0; i < M; i++){
			pos[i] = sc.nextInt();
			
			if(pos[i] >= 0){
				plus++;
			}else{
				minus++;
			}
		}
		
		int[] rights = new int[plus];
		int[] lefts = new int[minus];
		{
			int pc = 0, mc = 0;
			for(int i = 0; i < M; i++){
				if(pos[i] >= 0){
					rights[pc++] = pos[i];
				}else{
					lefts[mc++] = -pos[i];
				}
			}
		}
		
		Arrays.sort(rights);
		Arrays.sort(lefts);
		
		//System.out.println(Arrays.toString(rights));
		//System.out.println(Arrays.toString(lefts));
		
		long answer = Long.MAX_VALUE;
		for(int right_end = 0; right_end <= N; right_end++){
			if(right_end > rights.length){ continue; }
			
			final int left_end = N - right_end;
			if(left_end > lefts.length){ continue; }
			
			final long right_cost = right_end == 0 ? 0 : rights[right_end - 1];
			final long left_cost = left_end == 0 ? 0 : lefts[left_end - 1];
			
			final long fst_right = right_cost * 2 + left_cost;
			final long fst_left = left_cost * 2 + right_cost;
			
			answer = Math.min(answer, Math.min(fst_right, fst_left));
			//System.out.println(right_end + " " + left_end);
		}
		
		System.out.println(answer);
	}
	
	public static class Scanner implements Closeable {
		private BufferedReader br;
		private StringTokenizer tok;
 
		public Scanner(InputStream is) throws IOException {
			br = new BufferedReader(new InputStreamReader(is));
		}
 
		private void getLine() throws IOException {
			while (!hasNext()) {
				tok = new StringTokenizer(br.readLine());
			}
		}
 
		private boolean hasNext() {
			return tok != null && tok.hasMoreTokens();
		}
 
		public String next() throws IOException {
			getLine();
			return tok.nextToken();
		}
 
		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}
 
		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}
 
		public void close() throws IOException {
			br.close();
		}
	}
}
0