ZeroJudge h040 - 釣魚 解題心得( 題目 )
解題概念:二分搜、數學
解題方法:這題也是TOI的題目，注意這題雖然感覺很數學，但是我們可以利用二分搜的方式搜尋成功釣到魚的最小值。
注意事項:
(1)二分搜mid要開long(C++的long long int)，原因是左界、右界雖然都int，但是相加可能超過範圍。
(2)Java沒有以2為底的log，但是有以10為底的，根據換底公式:logab=logb/loga，另外先建表log過的朋友值會比較快(因為這樣log部分只要算一次)。
Java參考程式碼 (有更好意見可留言於下方，謝謝!)
//Author:En Chi Tsung(欉恩祁)
//Date:2022/01/20
import java.io.*;
import java.util.*;
public class zjh040 {
public static int ret,r,n,q;
public static long cnt,pre;
public static final double L=Math.log(2);
public static double[] f=new double[40005];
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
public static void main(String[] args) throws Exception{
n=readint();
for(int i=0;i<n;i++) {
f[i]=log2(readint()+1);
}
f[n]=0;
q=readint();
for(int i=0;i<q;i++) {
bw.write(BIS(readint())+"\n");
}
bw.flush();
}
public static int BIS(long x) {
long L=1,R=x,M;
while(L<R) {
M=(L+R)/2;
if(cal(M)>=x) {
R=M;
}
else {
L=M+1;
}
}
return (int)L;
}
public static long cal(long x) {
cnt=0;
pre=x;
for(int i=0;i<=n;i++) {
cnt+=pre;
pre=(int)Math.floor(pre*Math.min(f[i],30)/30);
if(pre<=0)break;
}
return cnt;
}
public static double log2(long x) {
return Math.log(x)/L;
}
public static int readint() throws Exception {
ret=0;
r=br.read();
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
return ret;
}
}
文章標籤
全站熱搜
