关于二分

二分的模板 :

                int l = 1 , r =cnt  ;
		int mid ; 
		while(l<=r){
			mid = (l+r)>>1 ; 
			if(check(mid)) {
				r = mid - 1 ; 
			}
			else {
				l = mid + 1 ;
			}
		}

看个题目 : (1010 只包含因子2 3 5的数)

K的因子中只包含2 3 5。满足条件的前10个数是:2,3,4,5,6,8,9,10,12,15。

所有这样的K组成了一个序列S,现在给出一个数n,求S中 >= 给定数的最小的数。

例如:n = 13,S中 >= 13的最小的数是15,所以输出15。

输入 第1行:一个数T,表示后面用作输入测试的数的数量。(1 <= T <= 10000) 第2 - T + 1行:每行1个数N(1 <= N <= 10^18) 输出 共T行,每行1个数,输出>= n的最小的只包含因子2 3 5的数。 输入样例 5 1 8 13 35 77 输出样例 2 8 15 36 80

题解 : 题目是求出 >= n 的最小的只包含因子 2 3 5 的数 , 因此打表借助二分就可解决,这里主要回顾一下二分。

图(一) 图(二)

图(三)

代码 :

#include <iostream>
#include <cstdio>
#include <algorithm> 
using namespace std ;
typedef long long LL;  
const LL inf = 0x3f3f3f3f3f3f3f3f; 
// 1010 
const LL maxn = 1e18+999 ; 
const int MAX = 50086 ; 
LL a[MAX] ;
LL cnt = 0 ; 
void init()
{
    LL i, j, k;
    for(i = 1; i < maxn; i*=2)
        for(j = 1; i*j < maxn; j*=3)
            for(k = 1; k*j*i < maxn; k*=5)
                a[cnt++] = i*j*k;
}
int main() {
	int t ; 
	init() ; // 打表 
	sort(a,a+cnt) ;
	cin >> t ; 
	LL n ; 
	while(t--) {
	
		scanf("%lld",&n);
		LL l = 1 , r =cnt  ;
		LL mid ; 
		while(l<=r){
			mid = (l+r)>>1 ; 
			if(a[mid] >=n) {
				r = mid - 1 ; 
			}
			else {
				l = mid + 1 ;
			}
		}
		
		printf("%lld\n",a[l]) ; 
	}

	return 0 ; 
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×