結果

問題 No.989 N×Mマス計算（K以上）
コンテスト
ユーザー usa1104_1224
提出日時 2020-03-07 19:29:31
言語 Java
(openjdk 23)
結果
WA  
実行時間 -
コード長 3,481 bytes
コンパイル時間 2,337 ms
コンパイル使用メモリ 77,540 KB
実行使用メモリ 56,824 KB
最終ジャッジ日時 2024-10-15 14:23:11
合計ジャッジ時間 10,019 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 2 WA * 16
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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);
		//２分探索
	    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(binary_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[]){
		//２分探索
		if(B.length == 1) {
			if(A*B[0]>=K) {
				return 0;
			}else {
				return -1;
			}			
		}
		
		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[]){
		//２分探索
				
				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;
			    if(B.length == 1) {
					if(A*B[0]>=K) {
						return 0;
					}else {
						return -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;
	}
}
0