| ||||||||||
Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:不需要 __int64,int 就够了,二分的时候把上界设为已知的最长段即可 47MSIn 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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator