题解-Atcoder-abc174e

本文章遵守知识共享协议 CC-BY-NC-SA ，同步发表于洛谷题解区，转载时须在文章的任一位置附上原文链接和作者署名（rickyxrc）。推荐在我的个人博客阅读。

题面大意

给定 $n$ 个数 $A_1,A_2,\cdots,A_n$，并给你 $k$ 次操作机会，每次你从 $A$ 中选择一个数 $a\in A$ 并指定一个实数 $t \in (0,a)$，在 $A$ 中删除 $a$ 并加入 $t$ 和 $a-t$，求使得 $A$ 中最大值最小的最小值。

图形化理解：给你 $n$ 条绳子，你需要切 $k$ 刀，求最长长度最短可以被切成多少。

解法

显然，我切的刀数越多，最长长度就会越小。

考虑二分答案，二分那个最大值，检验使得所有的值小于给定值的方案数能否小于要求的 $k$ 次，如果满足继续缩小右边界，不满足扩大左边界，直到两边界趋近于一个值为止。

为什么想到二分答案？

通常，我们会一个一个判断给定条件是否合法，复杂度为 $O(n^2)$，也就是遍历和检查的复杂度乘积。

而这里，题目的问题具有单调性，就是上文所说的切的越多，最长长度越小。

考虑二分答案，也就是二分可以的最长长度，计算出让所有长度小于那个长度的需要刀数，判断是否合法，再二分，直到找到答案为止。

我们要将一个数 $x$ 切成不大于 $l$ 的段，那么每次切的长度最大可以为 $l$，最少要切 $\lceil \frac{x}{l} \rceil-1$ 段，我们要判断是否合法，只需要计算 $\sum_{i=1}^n \lceil \frac{x_i}{l} \rceil-1$ 是否小于 $k$ 即可。

判断答案是否合法的函数就可以实现如下：

// 这里是指切成小于val的段的总刀数是否满足
bool check(double val)
{
  long long res = 0;
  for (long long i = 1; i <= n; i++)
    if (lenn[i] - val > 1e-3) // 注意精度
      res += (long long)(ceil(double(lenn[i]) / val)) - 1;
  return res <= k;
}

主函数也很好实现，但是记得注意精度！！

#include <stdio.h>
#include <math.h>
#define maxn 200007

long long lenn[maxn];
long long n, v, k, mx;
long long max(long long a, long long b)
{
  return a > b ? a : b;
}

signed main()
{
  scanf("%lld%lld", &n, &k);
  for (long long i = 1; i <= n; i++)
    scanf("%lld", lenn + i),
        mx = max(mx, lenn[i]);

  double l = 0, r = mx, mid;
  while (r - l > 1e-6)
  {
    mid = (l + r) / 2.0;
    if (check(mid))
      r = mid;
    else
      l = mid;
  }

  printf("%d", (long long)(mid + 1));
  return 0;
}