C++ 算法刷题：平方数、分组与拓扑排序

一、平方数

题目解析

题目给出一个数，找到离它最近的一个平方数并输出。

算法思路

一种思路是从 1 开始找，找到小于 x 的最大平方数 l 和大于 x 的最小平方数 r，比较差值。更简便的方法是利用 sqrt 函数：

我们知道 sqrt 函数可以对一个数进行开根号运算，返回 double 类型数据；

将该返回值强转为整型即拿到 l，再对其加一即拿到 r。

这样该数在区间 [ll, rr] 内，判断 rr - x 和 x - ll 哪个最小即可。

代码实现

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

int main() {
    long long x;
    cin >> x;
    long long a = sqrt(x);
    long long l = a * a, r = (a + 1) * (a + 1);
    if (x - l > r - x) cout << r << endl;
    else cout << l << endl;
    return 0;
}

二、分组

题目解析

题目描述：将 n 个同学分成 m 个组，每个同学擅长一个声部，同组同学可擅长不同声部，但同一声部的同学必须分在不同组（或理解为同声部人数限制）。目标是使每组人数尽可能少，若无法安排输出 -1，否则输出组中最多的人数。

题意转换：输入 n, m，表示 n 个人分 m 个组，随后 n 个数表示每个同学擅长的声调。

算法思路

初始思路尝试使用堆，但效率较低。正确的解决思路是二分答案：

假设每个组中最多有 x 人，若某声调有 y 人，则需分成 y/x 个组（向上取整）。

统计所有声调需要的总组数 sum。若 sum > m，说明 x 取小了，增大 x；若 sum <= m，说明可行，尝试减小 x。

在区间 [1, hmax] 中二分查找满足条件的最小 x。

代码实现

首先统计每种声调的人数及最大值 hmax。若声调种类数大于 m，直接输出 -1。否则使用二分查找。

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

int n, m;
unordered_map<int, int> cnt;

bool check(int x) {
    int sum = 0;
    for (auto& e : cnt) {
        sum += (e.second / x + (e.second % x == 0 ? 0 : 1));
    }
    return sum <= m;
}

int main() {
    cin >> n >> m;
    int hmax = 0;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        cnt[x]++;
        if (cnt[x] > hmax) hmax = cnt[x];
    }
    
    if (cnt.size() > m) {
        cout << -1 << endl;
    } else {
        int left = 1, right = hmax;
        while (left < right) {
            int mid = (left + right) / 2;
            if (check(mid)) right = mid;
            else left = mid + 1;
        }
        cout << left << endl;
    }
    return 0;
}

三、【模板】拓扑排序

题目解析

考查拓扑排序，给定包含 n 个点、m 条边的有向无环图，输出拓扑序列。

输入：n, m，随后 m 行每行两个整数 v1, v2 表示 v1 到 v2 的有向边。

算法思路

拓扑排序步骤：

1. 选择入度为 0 的节点输出。
2. 删除该节点及其发出的所有边。
3. 重复直至所有节点输出。

实现细节：

• 记录有向边：vector<vector<int>>，下标为起点，值为终点列表。
• 记录入度：vector<int>。
• 队列 queue 存放当前入度为 0 的节点。
• 结果存储：vector<int>，若最终大小等于 n 则存在拓扑序，否则输出 -1。

注意：输出结果时最后一个字符后不能有空格。

代码实现

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

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> arr(n + 1);
    vector<int> hash(n + 1);
    
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        hash[y]++;
        arr[x].push_back(y);
    }
    
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        if (hash[i] == 0) q.push(i);
    }
    
    vector<int> ret;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        ret.push_back(x);
        
        for (auto& e : arr[x]) {
            hash[e]--;
            if (hash[e] == 0) {
                q.push(e);
            }
        }
    }
    
    if (ret.size() == n) {
        for (int i = 0; i < ret.size(); i++) {
            cout << ret[i];
            if (i < ret.size() - 1) cout << ' ';
        }
        cout << endl;
    } else {
        cout << -1 << endl;
    }
    return 0;
}