Codeforces 551C

发表于 |

题目

有$N$堆东西排成一条直线，第$i$堆有$a_i$个东西。现有$M$个人，初始位于第$1$堆东西的左边，他们做一个操作需要$1$s的时间。每个人做的操作是独立的。

操作有$2$种：

  1. 向右走到下一堆东西。
  2. 若当前这堆东西不为空，则删除这堆中的$1$个东西。

问：这些人将这堆东西全部删除，最少要花多少时间。

数据范围

$1 \le N \le 10^5 \quad 0 \le a_i \le 10^9$

做法

求最小值，马上想到二分。这题显然可以二分答案。

那么如何check能否在给定的$t$时间内删完全部的东西呢？

一种想法是从前往后遍历每一堆东西，贪心地给这一堆分配所需的最少的人。但这样有个问题：在给右边某堆分配人员时，左边某堆可能有人员完成了工作，加入到了可分配人员中。这就需要维护一个可分配人员的信息。不好维护。

从左向右贪心

给堆分配人员不好做，我们试着考虑给人员分配堆，即：他在哪些堆中进行了删除操作。贪心地想：在给定的$t​$时间内，每个人应该要多做删除操作，少做移动操作。于是，我们遍历人员。对于每一个人，我们将其在$t​$时间内从左到右所能删除的东西逐渐删除。这样，当人员遍历结束后，若能删干净东西，则这个$t​$是可行的；否则不可行。

这个贪心的正确性证明的思路和下面一个贪心基本相似，都是从总时间之间的关系入手。这个贪心的总浪费时间$ \le n-1 < t$。所以也是最优的。

从右向左贪心

也是来自于上面的不可行的想法。从左向右给堆分配人员难做的点在于左边完成任务的人能够继续右移来完成右边的任务。那么，我们不妨考虑从右向左给堆分配人员，这样就可以消除这个问题。

代码

从左向右贪心

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int kMAXN = 1e5 + 5;
const int kMAXA = 1e9 + 5;
int N, M;
int a[kMAXN];
int b[kMAXN];
bool Check(LL t)
{
  for (int i = 0; i < N; ++i) {
    b[i] = a[i];
  }
  int j = 0;
  for (int i = 0; i < M; ++i) {
    LL t_remain = t;
    int pre_pos = -1;
    for (; j < N; ++j) {
      if (b[j] == 0) continue;
      int t_run = j - pre_pos;
      if (t_run < t_remain) {
        pre_pos = j;
        t_remain -= t_run;
        LL num_remove = min((LL)b[j], t_remain);
        b[j] -= num_remove;
        t_remain -= num_remove;
      }
      if (b[j] != 0) break;
    }
    if (b[j - 1] != 0) --j;
    if (j == N) return true;
  }
  return false;
}
LL BinarySeanch(LL l, LL r) // (l, r]
{
  while (r - l > 1) {
    LL mid = (l + r) / 2;
    if (Check(mid)) r = mid;
    else l = mid;
  }
  return r;
}
void Solve()
{
  LL ans = BinarySeanch(-1, (LL)N * kMAXA);
  printf("%lld\n", ans);
}
int main()
{
  scanf("%d%d", &N, &M);
  for (int i = 0; i < N; ++i) {
    scanf("%d", &a[i]);
  }
  Solve();
  return 0;
}

从右向左贪心

1
2