目录
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;
}