P4447. 分组

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 750 阅读时长 ≈ 3 分钟

考点

  • 贪心
  • 二分

题解

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
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int LEN = 1e5 + 10;

int cnt, in[LEN];

struct Node
{
    //每组的最后一个数字，组的长度
    int ed_, len_;
} arr[LEN];

int binary_search(int x)
{
    int l = 0, r = cnt - 1;
    while (l <= r)
    {
        int mid = l + (r - l) / 2;
        //每次将值插入到右边界，保证单调性
        if (arr[mid].ed_ <= x - 1)
            l = mid + 1;
        else
            r = mid - 1;
    }
    if (arr[r].ed_ != x - 1)
        return -1;
    return r;
}

int main()
{
    int n, idx;
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> in[i];
    sort(in, in + n);
    for (int i = 0; i < n; ++i)
    {
        if ((idx = binary_search(in[i])) == -1)
            arr[cnt].ed_ = in[i], arr[cnt++].len_ = 1;
        else
            arr[idx].ed_ = in[i], ++arr[idx].len_;
    }
    int ans = INT_MAX;
    for (int i = 0; i < cnt; ++i)
        ans = min(ans, arr[i].len_);
    cout << ans;
    return 0;
}

思路

又是一道经典的贪心好题，以输入{-3, -3, -2, -2, -1, 0, 1, 1, 2, 2, 3}为例；题眼有连续二字，先排序方便处理

题眼有使得人数最少的组人数最多，乍一看还以为是考二分；但本质上是贪心策略

因为重复的数字若不加处理，只能孤立；题目是想让我们尽可能地把原本孤立的数并到其他组里去

根据题意，每个组都是连续的，也就是升序；重复的数也是按序并入组内，所以用结构体记录每个组的最后一个及组的长度

1
2
3
4
5
struct Node
{
    //每组的最后一个数字，组的长度
    int ed_, len_;
} arr[LEN];

贪心策略也很明朗：

  • 遍历结构体数组，在满足最后一位数字等于当前数字减1的组中，将当前数插入到长度最小的
  • 否则新建一个组

纯暴力遍历结构体数组会超时；考虑到我们是对输入排序了的，且从小到大进行操作；每个组也是升序排列

那么只要保证结构体数组的下标从小到大时，每个组的最后一位数字形成的序列也是升序，即可通过二分来达到\(O\left( \log n \right)\)的遍历复杂度

所以，在进行二分查找时，应该寻找并插入的是右边界，这样才能维护单调性

并且，我们每次新建的组也处在右边界的位置，相同条件下新建组的长度更小，被插入的优先级也理应更高

按照上述例子，假设此刻要插入-1，请问选择左边界下标0还是右边界下标1的组呢？当然是右边界下标1啦

如果每次选择的是左边界，即下标0；结构体数组下标从小到大，每个组的最后一位数字形成的序列就不是单调的了，也就无法进行二分

如下图所示，此时形成的序列是1, -2, 1，没有单调性

如果选择右边界，形成的序列为-2, 1, 1，依旧遵守单调性！