Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

二分好题。。。贴Java代码。带注释

Posted by haqishen at 2015-01-13 19:25:46 on Problem 3685 and last updated at 2015-01-13 19:31:36
//注意到整个表中无论横竖,总是单调的。
//所以可以利用二重二分,时间复杂度 O(n*(log n)^2)
//第二重二分选择行或者列来进行都可以。请注意列是递增,行是递减
import java.util.*;
public class Main{
	static int N;
	static long M;
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		
		int T = s.nextInt();
		while(T-->0){			
			N = s.nextInt();
			M = s.nextLong();
			
//                      设定第一重二分的上下界
			long l = -25000000001l;
			long r =  25000000001l;
			
			while(r-l>1){
				long m = (l+r)/2;
//                              检验该m是否符合条件
				if(check(m)){
					r = m;
				}else{
					l = m;
				}
			}
			System.out.println(r);
		}
	}
	
	private static boolean check(long m) {
//              计算各列中共有多少个值小于等于m,并加在一起
//              然后判断该总数与M的大小关系
		long count = 0;
		for(int i = 1; i <= N;i++){
//                      对表格中的每列进行一次二分,找出该列有多少个数小于等于m并加入count
//                      也就是说每进行一次第一重二分,都要进行N次第二重二分
			count += binary(i,m);
		}
		if(count >= M){
			return true;
		}else{
			return false;
		}		
	}

	private static long binary(long i, long m) {
//              对表格中的每列进行一次二分,找出该列有多少个数小于等于m
		long lb = 0;
		long rb = N+1;
		while(rb - lb > 1){
			long mb = (lb+rb)/2;
			long ji = mb*mb + i*i + 100000*mb - 100000*i + mb*i;

			if(ji <= m){
				lb = mb;
			}else{
				rb = mb;
			}
		}
//              返回该行小于等于m的数的个数
		return lb;
	}

}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator