結果
問題 |
No.989 N×Mマス計算(K以上)
|
ユーザー |
![]() |
提出日時 | 2020-03-07 18:16:53 |
言語 | Java (openjdk 23) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,322 bytes |
コンパイル時間 | 2,150 ms |
コンパイル使用メモリ | 77,352 KB |
実行使用メモリ | 67,920 KB |
最終ジャッジ日時 | 2024-10-15 04:50:33 |
合計ジャッジ時間 | 11,407 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 2 WA * 16 |
ソースコード
import java.util.*; public class Main { static int N; static int M; static int K; public static void main(String args[] ){ Scanner sc =new Scanner(System.in); //2分探索 N = sc.nextInt(); M = sc.nextInt(); K = sc.nextInt(); String op = sc.next(); int B[] = new int[M]; int A[] =new int[N]; int ans = 0; for(int i = 0 ;i<B.length;i++) { B[i] = sc.nextInt(); } Arrays.sort(B); for(int i = 0 ;i<A.length;i++) { A[i] = sc.nextInt(); } Arrays.sort(A); if(op.equals("+")) { for(int i=0;i<A.length;i++) { if(Pbinary_search_find_closet(A[i],B)==-1) { }else { ans += B.length - binary_search_find_closet(A[i],B); } } }else { for(int i=0;i<A.length;i++) { if(Pbinary_search_find_closet(A[i],B)==-1) { }else { ans += B.length - Pbinary_search_find_closet(A[i],B); } } } System.out.println(ans); } public static int binary_search_find_closet(int A,int B[]){ //2分探索 if(B.length == 1)return 0; int min_diff=Integer.MAX_VALUE; int left = 0; int right =B.length-1; int min_diff_right=0; int min_diff_left=0; int closest_num=-1; while(left <= right) { int mid = left +(right-left)/2; //中心の左右の値と目標との差を計算する。 if (mid + 1 < B.length) { min_diff_right = B[mid+1]+A - K; } if (mid > 0) { min_diff_left = B[mid-1]+A - K; } // 最初の差と最も最小に近い値を更新する。 if (min_diff_left < min_diff && min_diff_left > 0) { min_diff = min_diff_left; closest_num = mid - 1; } if (min_diff_right < min_diff && min_diff_right > 0) { min_diff = min_diff_right; closest_num = mid + 1; } if (B[mid]+A < K) { left = mid + 1; }else if (B[mid]+A> K) { right = mid - 1 ; }else { return mid; } } return closest_num; } public static int Pbinary_search_find_closet(int A,int B[]){ //2分探索 if(B.length == 1)return 0; int min_diff=Integer.MAX_VALUE; int left = 0; int right =B.length-1; int min_diff_right=0; int min_diff_left=0; int closest_num=-1; while(left <= right) { int mid = left +(right-left)/2; //中心の左右の値と目標との差を計算する。 if (mid + 1 < B.length) { min_diff_right = B[mid+1]*A - K; } if (mid > 0) { min_diff_left = B[mid-1]*A - K; } // 最初の差と最も最小に近い値を更新する。 if (min_diff_left < min_diff && min_diff_left > 0) { min_diff = min_diff_left; closest_num = mid - 1; } if (min_diff_right < min_diff && min_diff_right > 0) { min_diff = min_diff_right; closest_num = mid + 1; } if (B[mid]*A < K) { left = mid + 1; }else if (B[mid]*A> K) { right = mid - 1 ; }else { return mid; } } return closest_num; } }