[アルゴリズム]プリアンブル1300-K回数
6791 ワード
1.質問
勢俊の大きさはN×N人配列Aをしました.配列内の数A[i][j]=i×jです.この数を主アレイBに入れると、Bの大きさはNとなる.×Nになる.Bを昇順に並べてみるとB[k]を求めてみる.
配列AとBのインデックスは1から始まる.
2.入力
最初の行は配列のサイズNを与える.Nは105以下の自然数である.2行目はkを与える.kはmin(109,N 2)の自然数以下である.
3.解答
二分探索で解決できる.
4.コード
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static long n,k;
public static long[] arr;
public static void main(String args[]) throws IOException{
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(bf.readLine());
k = Integer.parseInt(bf.readLine());
long left = 1;
long right = k;
while(left<right){
long mid =(left+right)/2;
long count =0;
for(int i=1;i<=n;i++){
count+=Math.min(mid/i,n);
}
if(k<=count){
right = mid;
}
else{
left = mid+1;
}
}
System.out.println(left);
}
}
Reference
この問題について([アルゴリズム]プリアンブル1300-K回数), 我々は、より多くの情報をここで見つけました https://velog.io/@yeju6540/알고리즘-백준-1300-K번째-수テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol