結果

問題 No.370 道路の掃除
ユーザー uafr_csuafr_cs
提出日時 2017-10-29 22:23:07
言語 Java21
(openjdk 21)
結果
AC  
実行時間 61 ms / 2,000 ms
コード長 2,508 bytes
コンパイル時間 3,665 ms
コンパイル使用メモリ 75,156 KB
実行使用メモリ 51,120 KB
最終ジャッジ日時 2023-08-14 09:55:09
合計ジャッジ時間 5,618 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 43 ms
49,480 KB
testcase_01 AC 44 ms
49,412 KB
testcase_02 AC 44 ms
49,464 KB
testcase_03 AC 44 ms
49,452 KB
testcase_04 AC 44 ms
49,572 KB
testcase_05 AC 43 ms
49,420 KB
testcase_06 AC 44 ms
49,528 KB
testcase_07 AC 43 ms
49,496 KB
testcase_08 AC 43 ms
49,444 KB
testcase_09 AC 44 ms
49,720 KB
testcase_10 AC 46 ms
49,452 KB
testcase_11 AC 46 ms
49,628 KB
testcase_12 AC 45 ms
49,540 KB
testcase_13 AC 45 ms
49,460 KB
testcase_14 AC 45 ms
49,420 KB
testcase_15 AC 46 ms
49,452 KB
testcase_16 AC 46 ms
49,520 KB
testcase_17 AC 45 ms
49,536 KB
testcase_18 AC 45 ms
49,428 KB
testcase_19 AC 46 ms
49,376 KB
testcase_20 AC 57 ms
50,552 KB
testcase_21 AC 55 ms
50,432 KB
testcase_22 AC 52 ms
50,188 KB
testcase_23 AC 53 ms
50,320 KB
testcase_24 AC 46 ms
49,904 KB
testcase_25 AC 50 ms
49,464 KB
testcase_26 AC 57 ms
49,916 KB
testcase_27 AC 48 ms
49,844 KB
testcase_28 AC 49 ms
49,388 KB
testcase_29 AC 53 ms
50,340 KB
testcase_30 AC 61 ms
51,120 KB
testcase_31 AC 52 ms
50,196 KB
testcase_32 AC 54 ms
50,260 KB
testcase_33 AC 61 ms
50,556 KB
権限があれば一括ダウンロードができます

ソースコード

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