Cable master POJ - 1064 题解

冷不防 2022-09-02 04:16 163阅读 0赞

# 题目链接 #

https://vjudge.net/problem/POJ-1064

当然我是在Virtual Judge上面写的，可以直接去POJ去提交。

这个题目感觉并不是很困难的样子，主要就是一个二分的思想，之前写的时候，主要是结尾判断的时候，没有向下取整，直接四舍五入的，导致一直提交失败，甚至写了不只一个版本的代码。

下面，我随便给出两个版本的结果，都能过。

#include <iostream>
    #include <cstdio>
    #include <cmath>
    
    using namespace std;
    
    int N, K;
    const int MAX_N = 10000;
    double L[MAX_N];
    
    bool binary_search_L(double mid_L)
    {
        
    	int total = 0;
    	for (int i = 0 ; i < N; ++i)
    	{
        
    		total += int(L[i] / mid_L);
    	}
    	return total >= K;
    }
    
    void solve()
    {
        
    	double min_L = 0;
    	double max_L = 10000000;
    	
    	for (int i =  0; i < 200; ++i)
    	{
        
    		double mid_L = (min_L + max_L) / 2;
    		if (binary_search_L(mid_L))
    		{
        
    			min_L = mid_L;
    		}
    		else
    		{
        
    			max_L = mid_L;
    		}
    	}
    	cout.setf(ios_base::fixed);
    	cout.precision(2);
    	cout << floor(min_L *100) / 100 << endl;
    	//printf("%.2f",min_L);
    }
    
    int main()
    {
        
    	ios::sync_with_stdio(false);
    	cin.tie(0);
    	cin >> N;
    	cin >> K;
    	for (int i = 0; i < N; ++i)
    	{
        
    		cin >> L[i];
    	}
    	
    	solve();
    	
    	return 0;
    }

#include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <iomanip>
    #include <cmath>
    
    using namespace std;
    
    const int N = 10000+10;
    const int K = 10000+10;
    int n,k;
    
    double a[N];
    
    bool greed(double mid)
    {
        
        int cnt=0;
        for(int i=0;i<n;++i)
        {
        
            cnt+=int(a[i]/mid);
        }
        if(cnt>=k)
            return true;
        else{
        
            return false;
        }
    }
    
    double Find()
    {
        
        double l=0,r=100010;
        while(r-l>1e-5)
        {
        
            double mid=(r+l)/2;
            if(greed(mid))
            {
        
                l=mid;
            }
            else
            {
        
                r=mid;
            }
        }
        return r;
    }
    
    int main()
    {
        
        double Max=-1;
        cin>>n>>k;
        for(int i=0;i<n;i++)
        {
        
            scanf("%lf",&a[i]);
            if(a[i]>Max){
        
                Max=a[i];
            }
        }
        sort(a,a+n);
        printf("%.2f\n",floor(Find()*100)/100);
        //cout<<setiosflags(ios::fixed)<<setprecision(2);
        //cout<<Find(Max)<<endl;
        return 0;
    }