posts - 33,  comments - 33,  trackbacks - 0
题意:烘干机,给出一堆衣服的水分a[i],在不加烘干机情况下自动每一分钟减少1水分,每分钟可以变改衣服(i)到烘干机中,每分钟减少k水分,求最少需要多少时间。
题解:第一时间就想到使用二分枚据答案+验证这种思路,不过这题还是有些陷阱需要注意。
1. 验证答案时,如果 a[i] <= mid,让它自然烘干即可 ; 如果a[i] > mid,那么烘干这件衣服可以分成两段时间:使用烘干机时间x1 + 自然烘干时间x2,那么可以列出等式:mid = x1 + x2; a[i] <= kx1+x2;于是得x1 >= (a[i] -mid)/(k-1);即得使用烘干机的最少时间x1
2.注意当k==1时,k-1 == 0,需要特殊处理,直接打出ans = maxV
3.注意当求left+right时,结果可能超出范围,正确的方法应该是left + (right - left)*0.5;
#include <stdio.h>

const int N = 100005;
int n;
int a[N];
int k;

bool check(int _value)
{
    
int cnt = 0;
    
for (int i = 0; i < n; ++i)
    
{
        
if (a[i] > _value)
        
{
            
double kk = ((double)(a[i] - _value))/(k-1);
            cnt 
+= (int)kk;
            
if (kk - (int)kk > 0)
            
{
                
++cnt;
            }

            
if (cnt > _value)
            
{
                
return false;
            }

        }

    }


    
return (cnt <= _value);
}


int BinarySearch(int _low,int _high)
{
    
int left = _low;
    
int right = _high;
    
int mid;
    
int ans = _high;
    
while(left <= right)
    
{
        mid 
= (left+(right-left)*0.5);
        
if (check(mid))
        
{
            ans 
= mid;
            right 
= mid - 1;
        }

        
else
        
{
            left 
= mid + 1;
        }

    }

    
return ans;
}


void Test()
{
    
int maxV = 0;
    
for (int i = 0; i < n; ++i)
    
{
        scanf(
"%d",&a[i]);
        
if (maxV < a[i])
        
{
            maxV 
= a[i];
        }

    }

    scanf(
"%d",&k);
    
if (k == 1)
    
{
        printf(
"%d\n",maxV);
    }

    
else
        printf(
"%d\n",BinarySearch(0,maxV));
}


int main()
{
    
while(scanf("%d",&n) != EOF)
    
{
        Test();
    }

    
return 0;
}


posted on 2011-11-09 12:45 bennycen 阅读(1473) 评论(1)  编辑 收藏 引用 所属分类: 算法题解

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理