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

Re:不需要 __int64,int 就够了,二分的时候把上界设为已知的最长段即可 47MS

Posted by JC1524949 at 2013-05-22 15:50:03 on Problem 1064
In Reply To:不需要 __int64,int 就够了,二分的时候把上界设为已知的最长段即可 47MS Posted by:xmjt621 at 2009-05-09 14:05:10
> #include <cstdio>
> 
> #define MAXN 10000
> 
> int _ns[MAXN];
> int _k, _n, _maxL = 0, _res = 0;
> 
> void Ipt()
> {
> 	scanf("%d%d", &_n, &_k);
> 	double ipt;
> 	for (int i = 0; i < _n; ++i)
> 	{
> 		scanf("%lf", &ipt);
> 		_ns[i] = int(ipt * 100);
> 		if (_maxL < _ns[i])
> 		{
> 			_maxL = _ns[i];
> 		}
> 	}
> }
> 
> inline void Opt()
> {
> 	printf("%.2lf\n", double(_res) / 100.0);
> }
> 
> bool Test(int len)
> {
> 	int i, j, t;
> 	for (i = 0, j = 0; i < _n && j < _k; ++i)
> 	{
> 		t = _ns[i];
> 		while (j < _k && t >= len)
> 		{
> 			t -= len;
> 			++j;
> 		}
> 	}
> 	if (j < _k)
> 	{
> 		return false;
> 	}
> 	if (_res < len)
> 	{
> 		_res = len;
> 	}
> 	return true;
> }
> 
> void BinarySearch()
> {
> 	int begin = 0;
> 	int end = _maxL + 1;
> 	int mid;
> 	while (begin != end)
> 	{
> 		mid = ((begin + end) >> 1);
> 		if (Test(mid))
> 		{
> 			begin = mid + 1;
> 		}
> 		else
> 		{
> 			end = mid;
> 		}
> 	}
> }
> 
> int main()
> {
> 	Ipt();
> 	BinarySearch();
> 	Opt();
> 	return 0;
> }

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