首页 > 代码库 > hdu1316 How Many Fibs?
hdu1316 How Many Fibs?
//思路就是大整数数组保存fib数,然后二分查找import java.util.*;import java.math.*;import java.io.*;class Main { public static void main(String[] args) { // TODO Auto-generated method stub BigInteger[] f = new BigInteger[500]; f[0]=f[1]=BigInteger.ONE; for(int i=2;i<500;i++) f[i]=f[i-1].add(f[i-2]); f[0]=BigInteger.ZERO; Scanner sc = new Scanner(new BufferedInputStream(System.in)); BigInteger l,r; while(sc.hasNext()) { l = sc.nextBigInteger(); r = sc.nextBigInteger(); if(l.compareTo(BigInteger.ZERO)==0&&r.compareTo(BigInteger.ZERO)==0) break; int ansl = Arrays.binarySearch(f,l ); int ansr = Arrays.binarySearch(f, r); if(ansl<0) ansl=-ansl-2; if(ansr<0) ansr=-ansr-2; if(Arrays.binarySearch(f, l)>0) ansl--; System.out.println(ansr-ansl); } }}
附Arrays.binarySearch()的用法:
public static int binarySearch(Object[] a,Object key) 使用二分搜索法来搜索指定数组，以获得指定对象。在进行此调用之前，必须根据元素的自然顺序对数组进行升序排序（通过 sort(Object[]) 方法）。如果没有对数组进行排序，则结果是不确定的。（如果数组包含不可相互比较的元素（例如，字符串和整数），则无法 根据其元素的自然顺序对数组进行排序，因此结果是不确定的。）如果数组包含多个等于指定对象的元素，则无法保证找到的是哪一个。
参数：a - 要搜索的数组key - 要搜索的值
返回：如果它包含在数组中，则返回搜索键的索引；否则返回 (-(插入点) - 1)。 插入点 被定义为将键插入数组的那一点：即第一个大于此键的
元素索引，如果数组中的所有元素都小于指定的键，则为 a.length。注意，这保证了当且仅当此键被找到时，返回的值将 >= 0。
否则返回 (-(插入点) - 1)这句话要注意：要是查询的的值小于数组里面
的最小值那么结果(-(0)-1结果就是-1)，如果查询的 值大于数组里面的最大值。那么结果就是(-(它的索引值)-1结果就是-(1+索引值))
hdu1316 How Many Fibs?
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。