stl模板之queue实例一：最少个数

### 回答1：
题目描述：

给定一个数组，每次可以选择其中的一个数，将其除以2（如果是奇数则向下取整），问最少需要几次操作可以将所有数变为偶数。

输入格式：

第一行包含一个整数n，表示数组长度。

第二行包含n个整数，表示数组中的元素。

输出格式：

输出一个整数，表示最少需要的操作次数。

样例输入：

5
5 6 8 10 12

样例输出：

2

解题思路：

对于每个数，我们可以不断地除以2，直到它变成偶数为止。因此，我们可以将所有数都不断地除以2，直到它们不能再被2整除为止。这样，我们就可以得到所有数的最少操作次数。

具体实现时，我们可以使用一个队列来存储所有的数，然后不断地将队首元素除以2，直到它不能再被2整除为止。然后，我们将它从队列中弹出，并将它的操作次数累加到答案中。最后，当队列为空时，我们就得到了所有数的最少操作次数。

代码实现：

### 回答2：
题目描述：

给定一个长度为n的整数序列，和一个正整数k，从序列中选取最少的数字，使得每相邻的k个元素中至少有一个数字被选中。例如，序列{1,2,3,4,5,6}和k=2，则需要选中数字1、3、5。

解题思路：

由题目中的描述可以看出，需要选取的数字要尽量少，因此可以从头开始遍历整个序列，在遍历到一个数字时，将该数字入队，同时记录该数字是否被选中，也就是在队列中是否有该数字。如果队列中已经有了这个数字，就可以判定该数字不需要被选中，继续遍历序列；否则可以将队列中最早入队的数字弹出，同时标记该数字被选中。当遍历到一个位置时，队列中的数字个数为k时，可以选取队头元素，同时将队头元素弹出。最后统计被选中的数字的个数即可。

实现代码：

#include <iostream>
#include <queue>
using namespace std;

int main()
{
    int n, k;
    cin >> n >> k;
    queue<int> q;
    bool vis[100005] = {0}; // vis数组用于记录数字是否被选中
    int cnt = 0; // 记录被选中的数字的个数
    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        if (vis[x]) continue; // 如果数字已经被选中，则进入下一次循环
        q.push(x); // 将数字入队
        if (q.size() == k) // 队列中元素个数达到k时，选取队头元素
        {
            cnt++;
            vis[q.front()] = true; // 将队头元素标记为已选中
            q.pop(); // 弹出队头元素
        }
    }
    cout << cnt << endl;
    return 0;
}

此代码的时间复杂度为O(n)，空间复杂度为O(k)。

### 回答3：
问题描述：

有n个人要进行游戏，每次游戏需要选出一名队长和若干名队员，为了使得每个人都有机会成为队长，需要将n个人按顺序分成k组进行游戏，请问每组队员最少需要多少人？

分析：

该问题可以采用贪心算法来解决。因为每个人都有机会成为队长，所以每k个人中必须有一名队长，而剩余的k-1个人则作为队员。因此，我们可以先将每k个人中的最后一个作为队长，然后将前面k-1个人作为队员，这样就得到了一组解，将该组解中的队员数累加起来就是该解对应的队员数。接下来，我们再对剩余人数对k取余，如果余数不为0，则还需要添加一组队伍，那么该组队员数就是剩余人数对k取余的结果，如果余数为0，则不需要再添加一组队伍了，这时候所有解对应的队员数中最小的那个就是答案。

代码实现：

我们可以使用STL模板中的queue来实现该算法，具体代码实现如下：