| ||||||||||
| 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