Решение задачи "Провода" с Меньшиков

Без пояснения   Просмотров: 16


Дано N отрезков провода длиной L1, L2, ..., LN сантиметров. Требуется с помощью разрезания получить из них K равных отрезков как можно большей длины, выражающейся целым числом сантиметров. Если нельзя получить K отрезков длиной даже 1 см, вывести 0.

Ограничения: 1 <= N <= 10 000, 1 <= K <= 10 000, 100 <= Li <= 10 000 000, все числа целые.

Код

#include <iostream>
#include <cstdio>
#include <vector>
 
using namespace std;
 
int n,amount;
vector<int>  mas;
void input()
{
    cin>>n>>amount;
    mas.resize(n);
    for (int i=0;i<n;i++)
        scanf("%d", &mas[i]);
}
int calc(int len, vector<int> &mas)
{
    int res = 0;
    for (int i=0;i<mas.size();i++)
        res += mas[i]/len;
    return res;
}
void solve()
{
    int l = 0, r = 1e8;
    int len = 0;
    while (l<=r)
    {
        int m = (l+r)>>1;
        if (m == 0)
        {
            l = m+1;
            continue;
        }
        int curAmount = calc(m,mas);
        if (curAmount < amount)
            r = m - 1;
        else if (curAmount >= amount)
        {
            l = m + 1;
            len = max(len,m);
        }
    }
    cout<<len;
}
int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
 
    input();
    solve();
    return 0;
}

         

 Администратор Photo Автор: Администратор


Отправить решение задачи
Чтобы отправить решение вам нужно войти в систему или зарегистрироваться

Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться