平方数

牛妹是一个喜欢完全平方数的女孩子。
牛妹每次看到一个数 x，都想求出离 x 最近的完全平方数 y。
每次手算太麻烦，所以牛妹希望你能写个程序帮她解决这个问题。
形式化地讲，你需要求出一个正整数 y，满足 y 可以表示成 a2a^2a2（a 是正整数），使得 |x-y| 的值最小。可以证明这样的 y 是唯一的。

输入描述:

一行，一个整数 x (1≤x≤1012)x\ (1\le x\le 10^{12})x (1≤x≤1012)，表示牛妹询问的数。

输出描述:

一行，一个整数 y，表示离 x 最近的完全平方数 y。

#include <iostream>
#include <cmath>
#define int long long
using namespace std;signed main()
{int n;cin>>n;int x = sqrt(n);int a = x*x,b = (x+1)*(x+1);cout<<(n-a<b-n?a:b)<<endl;return 0;
}

---

分组

dd当上了宣传委员，开始组织迎新晚会，已知班里有nnn个同学，每个同学有且仅有一个擅长的声部，把同学们分成恰好mmm组，为了不搞砸节目，每一组里的同学都必须擅长同一个声部，当然，不同组同学擅长同一个声部的情况是可以出现的，毕竟一个声部也可以分成好几个part进行表演，但是他不希望出现任何一组的人过多，否则可能会导致场地分配不协调，也就是说，她希望人数最多的小组的人尽可能少，除此之外，对组内人员分配没有其他要求，她希望你告诉她，这个值是多少，如果无法顺利安排，请输出-1

输入描述:

第一行两个数个数n,m(1≤m≤n≤100000)表示人数
接下来一行n个数,a[i](1≤a[i]≤n)表示第i个学生的擅长声部

输出描述:

输出一个数，表示人数最多的小组的人数

//暴力做法#include <bits/stdc++.h>using namespace std;
int n,m;
unordered_map<int,int>hx;bool check(int x)
{int g = 0;for(auto&[a,b]:hx){g += b/x + (b%x==0?0:1);}return g<=m;
}
int main()
{cin>>n>>m;int h = 0;for(int i = 0;i<n;++i){int x;cin>>x;h = max(h,++hx[x]);}if(m<hx.size()){cout<<-1;}else{for(int i = 1;i<=h;++i){if(check(i)){cout<<i;break;}}}return 0;
}

//二分做法#include <bits/stdc++.h>using namespace std;
int n,m;
unordered_map<int,int>hx;bool check(int x)
{int g = 0;for(auto&[a,b]:hx){g += b/x + (b%x==0?0:1);}return g<=m;
}
int main()
{cin>>n>>m;int h = 0;for(int i = 0;i<n;++i){int x;cin>>x;h = max(h,++hx[x]);}if(m<hx.size()){cout<<-1;}else{int l = 1,r = h;while(l<r){int mid = l+r>>1;if(check(mid))r = mid;else l = mid+1;}cout<<l;}return 0;
}

---

拓扑排序

给定一个包含�n个点�m条边的有向无环图，求出该图的拓扑序。若图的拓扑序不唯一，输出任意合法的拓扑序即可。若该图不能拓扑排序，输出−1−1。

输入描述：

第一行输入两个整数�,�n,m ( 1≤�,�≤2⋅1051≤n,m≤2⋅105)，表示点的个数和边的条数。
接下来的�m行，每行输入两个整数��,��u**i​,v**i​ (1≤�,�≤�1≤u,v≤n)，表示��u**i​到��v**i​之间有一条有向边。

输出描述：

若图存在拓扑序，输出一行�n个整数，表示拓扑序。否则输出−1−1。

#include <bits/stdc++.h>using namespace std;
int n, m;
const int N = 2e5 + 10;
vector<vector<int> >edges(N);
int in[N];
queue<int>q;
vector<int>ans;int main() {cin >> n >> m;for (int i = 0; i < m; ++i) {int u, v;cin >> u >> v;edges[u].push_back(v);in[v]++;}for (int i = 1; i <= n; ++i) {if (in[i] == 0) {q.push(i);}}while (!q.empty()) {int t = q.front();q.pop();ans.push_back(t);for (int& x : edges[t]) {if (--in[x] == 0) {q.push(x);}}}if (ans.size() == n) {for (int i = 0; i < n - 1; i++) {cout << ans[i] << " ";}cout << ans[n - 1]; // 测评会考虑最后⼀个元素的空格} else {cout << -1 << endl;}return 0;
}