题解 | #分组#_牛客博客

题目链接

分组

题目描述

有 $n$ 个同学，老师要把他们分成若干组。

每个组的同学数量必须不少于 3 个人。

请问这 $n$ 个同学最多可以分成多少组。

解题思路

这是一个简单的最优化问题，可以通过贪心策略来解决。

核心思想

我们的目标是最大化分组的数量。

为了让分出的组数最多，我们应该让每个组包含的人数最少。

根据题目要求，每个组的同学数量不少于 3 人，所以每个组的最少人数就是 3 人。

推导

因此，最优的策略就是尽可能多地分出“3人小组”。

对于 $n$ 个同学，我们可以分出的小组数量就是 $n$ 除以 3 的整数商。

例如，如果有 8 个同学，8 / 3 = 2。我们可以分出 2 个小组（比如一个 3 人组，一个 5 人组，或者两个 4 人组），剩下的同学无法再组成新的小组。

所以，最终的答案就是 $n / 3$ 。

代码

c++
java
python

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    cout << n / 3 << endl;

    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(n / 3);
    }
}

import sys

def solve():
    n_str = sys.stdin.readline()
    if not n_str:
        return
    n = int(n_str)
    print(n // 3)

solve()

算法及复杂度

算法：数学 / 贪心
时间复杂度: $\mathcal{O}(1)$ ，因为只需要进行一次整数除法运算。
空间复杂度: $\mathcal{O}(1)$ 。