P2440 木材加工

秒速五厘米 2022-10-12 04:28 135阅读 0赞

**题目背景**  
要保护环境

**题目描述**  
木材厂有一些原木，现在想把这些木头切割成一些长度相同的小段木头（木头有可能有剩余），需要得到的小段的数目是给定的。当然，我们希望得到的小段木头越长越好，你的任务是计算能够得到的小段木头的最大长度。木头长度的单位是cm。原木的长度都是正整数，我们要求切割得到的小段木头的长度也是正整数。

例如有两根原木长度分别为11和21，要求切割成到等长的6段，很明显能切割出来的小段木头长度最长为5.

**输入格式**  
第一行是两个正整数N和K(1 ≤ N ≤ 100000，1 ≤ K ≤ 100000000)，N是原木的数目，K是需要得到的小段的数目。

接下来的N行，每行有一个1到100000000之间的正整数，表示一根原木的长度。

**输出格式**  
能够切割得到的小段的最大长度。如果连1cm长的小段都切不出来，输出”0”。

**输入输出样例**  
**输入**

3 7
    232
    124
    456

**输出**

114

# 60分代码 #

#include <iostream>
    #include <cstring>
    #include <cstdio>
    #include <algorithm>
    
    using namespace std;
    #define LL long long
    LL n, k;
    const LL value = 100000001;
    LL a[100001];
    bool check(LL t)
    { 
        LL tmp = 0;
        for (int i = 0; i < n; i++)
        { 
            tmp += a[i] / t;
        }
        if (tmp >= k)
            return true;
        else
            return false;
    }
    int main()
    { 
        cin >> n >> k;
        for (int i = 0; i < n; i++)
        { 
            cin >> a[i];
        }
        int l = 0, r = value - 1;
        int mid;
        while (l < r)
        { 
            mid = (l + r) / 2;
            if (check(mid))
            { 
                l = mid;
            }
            else
            { 
                r = mid - 1;
            }
        }
        cout << l << endl;
        return 0;
    }

# 100分代码 #

#include <queue>
    #include <stack>
    #include <cmath>
    #include <string>
    #include <cstdio>
    #include <cstring>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    #define LL long long
    LL n, k;
    LL a[1000005];
    
    bool f(LL x)
    { 
        LL ans = 0;
        for (int i = 1; i <= n; i++)
        { 
            ans += a[i] / x;
        }
        return ans >= k;
    }
    
    int main()
    { 
        cin >> n >> k;
        for (int i = 1; i <= n; i++)
            cin >> a[i];
    
        LL l = 0, r = 100000001;
        LL mid;
    
        while (l + 1 < r)
        { 
            mid = (l + r) / 2;
            if (f(mid))
                l = mid;
            else
                r = mid;
        }
        cout << l << endl;
        return 0;
    }