C++笔试强训day15

目录

1.平方数

2.分组

Check函数的具体实现：

3.拓扑排序

1.平方数

链接

数学找规律，找离 x 最近的完全平方数 y。

先开平方根再利用四舍五入进位即可。

详细代码：

#include <cmath>
#include <iostream>
using namespace std;
#define int long long
signed main() {
	int x;
	cin >> x;
	int tmp = (int)(sqrt(x) + 0.5);
	cout << tmp * tmp << endl;
}

2.分组 ​​​​​​​

链接

首先想到的肯定是暴力枚举：

从1 到 max_cnt（最大的声部人数）遍历，一个一个判断，第一个满足条件的即可cout了，因为求的是最多小组人数尽可能小。

从左往右遍历大数据很有可能超时，这时就要去想办法优化，二分就是个很好的选择：

暴力：

优化 -> 二分：

详细代码：

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

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

bool Check(int x) // 每组人数最多为x时
{
    int g = 0;
    for (auto& [a, b] : umap)
    {
        g += b / x + (b % x == 0 ? 0 : 1);
    }
    return g <= m;
}

int main()
{
    cin >> n >> m;

    int x;
    int maxn = 0;
    for (int i = 0; i < n; ++i)
    {
        cin >> x;
        maxn = max(maxn, ++umap[x]);
    }
    int kinds = umap.size();
    if (kinds > m)
        cout << -1 << endl;
    else
    {
        if (kinds == m)
            cout << maxn << endl;
        else
        {
             暴力
            //for (int i = 1; i <= maxn; ++i)
            //{
            //    if (Check(i))
            //    {
            //        cout << i << endl;
            //        break;
            //    }
            //}
            int l = 1;
            int r = maxn;
            while (l < r)
            {
                int mid = l + (r - l) / 2;
                if (Check(mid))
                    r = mid;
                else
                    l = mid + 1;
            }
            cout << l << endl;
        }
    }
    return 0;
}

Check函数的具体实现：

依次取出umap（哈希表）中的数的次数，用次数 除以 x则可以得到可以分多少组，然后如果有余数的话就再可以分一组：

for ( auto & [a, b] : umap)

{

        g += b / x + (b % x == 0 ? 0 : 1 );

}

返回值则是g <= m, 因为大于m就不满足题意，小于m的话可以通过无限分组（拆开那些同一个声部）来实现。

注意：那为什么g < m 时一定能凑出来等于m呢：

因为n是 >= m的，将n完全拆开是肯定可以拼凑出m组的。

3.拓扑排序

链接

一道拓扑排序模板题，了解过拓扑排序就能很简单写出来。

就分三步：

1.构图

2.将入度为 0 的数存入队列

3.BFS遍历，取数出来 cout 然后，将该数连接的线去除

        同时若出现入度为 1 的数，接着存入队列。

详细代码：

#include <iostream>
#include <queue>
#include <vector>
#include <unordered_map>
using namespace std;
const int N = 2e5 + 10;

int n, m, a, b;
int in[N];
int ret[N];
int k = 0;
int main() {
    cin >> n >> m;

    // 构图
    unordered_map<int, vector<int>> edges;
    for (int i = 0; i < 2 * (n - 1); ++i)
    {
        cin >> a >> b;
        edges[a].push_back(b);
        in[b]++;
    }

    // 存入度为一的数
    queue<int> q;
    for (int i = 1; i <= n; ++i)
        if (in[i] == 0)
            q.push(i);

    while (q.size())
    {
        int top = q.front();
        q.pop();

        ret[k++] = top;
        for (int e : edges[top])
        {
            in[e]--;
            if (in[e] == 0)
                q.push(e);
        }
    }

    int flag = 1;
    for (int i = 1; i <= n; ++i)
        if (in[i] != 0)
        {
            cout << -1 << endl;
            flag = 0;
            break;
        }

    if (flag)
    {
        for (int i = 0; i < k - 1; ++i)
            cout << ret[i] << " ";
        cout << ret[k - 1];
    }

    return 0;
}