Kattis - fence2【二分法】

Kattis - fence2【二分法】

题意

有一个农夫需要建造一个 N - 1 米长的篱笆，需要 N 根柱子，然后有 K 根 柱子 需要将这 K 根柱子 切成 N 段 然后 要尽量保证这 N 段柱子的长度尽量长，并且这 N 段柱子的长度是相等的 然后求最少需要切几次。注意：柱子的长度可以是浮点数。

思路

用二分法找答案，然后再求和 不过要注意的是 ，如果柱子原来的长度与要分成的柱子的长度是可以整除的 那么切的刀数 就是 N/MAX - 1

AC代码

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cmath>

#include <deque>

#include <vector>

#include <queue>

#include <string>

#include <cstring>

#include <map>

#include <stack>

#include <set>

#include <cstdlib>

#include <ctype.h>

#include <numeric>

#include <sstream>

using namespace std;

typedef long long LL;

const double PI  = 3.14159265358979323846264338327;

const double E   = 2.718281828459;

const double eps = 1e-6;

const int MAXN   = 0x3f3f3f3f;

const int MINN   = 0xc0c0c0c0;

const int maxn   = 1e4 + 5;

const int MOD    = 1e9 + 7;

int arr[maxn];

int n, k;

bool check(double mid)

{

    int sum = 0;

    for (int i = 0; i < k; i++)

    {

        int temp = (int)(1.0 * arr[i] / mid);

        if (fabs(1.0 * temp * mid - 1.0 * arr[i]) <= eps)

            temp--;

        sum += temp;

    }

    if (sum >= n)

        return true;

    return false;

}

int main()

{

    scanf("%d%d", &k, &n);

    memset(arr, 0, sizeof(arr));

    for (int i = 0; i < k; i++)

        scanf("%d", &arr[i]);

    double l = 0, r = (double)n;

    double mid;

    double MAX = MINN;

    while (r - l >= eps)

    {

        mid = (l + r) / 2.0;

        if (check(mid))

        {

            MAX = max(MAX, mid);

            l = mid;

        }

        else

            r = mid;

    }

    LL ans = 0;

    for (int i = 0; i < k; i++)

    {

        int temp = (int)(1.0 * arr[i] / MAX);

        if (fabs(1.0 * temp * MAX - 1.0 * arr[i]) <= 1e-1)

            temp--;

        ans += temp;

    }

    cout << ans << endl;

}