1.平方数
水题直接看代码
代码：
#define _CRT_SECURE_NO_WARNINGS 1 #include <iostream> #include<math.h> #include<algorithm> using namespace std; typedef long long ll; int main() { ll x; cin >> x; ll a = sqrt(x); if (abs(a * a - x) < abs((a + 1) * (a + 1) - x)) { cout << a * a << endl; } else { cout << (a + 1) * (a + 1) << endl; } return 0; }
2.分组
思路：
一眼二分。一般来说，遇到什么最大属性集合里面求最小都可以考虑用二分。
这题求人数最多的小组的人尽可能少。
我们将每一次分组情况都视为一次二分。每次二分的mid表示当前的所有分组中，拥有最多人数的组的人数。以此为基准，对所有的人进行分组，看能不能至少凑成m组，且这m组的每组最多人数不超过mid。
分组如何分呢？如果某一个声部的人数超过mid，我们就把超过的部分添加到新的一组去。如果人数小于或者等于mid,那就让他们一起为一组。
这样分可以得到以下结论：所有分组的最多人数不超过mid。且这样分组，组的数量是最少的。
如果按最少分组的数量都能大于m,说明我一定不能能把这些分组拆成恰好m个。
如果按最少分组的数量<m。无非就是从每组割一点人出来组成新的一组嘛。比如让一部分人一个人一组嘛。
我们把能分组成功的mid都放在右边。不能分组成功的都放在左边。
等到二分结束。r一定是在所有可以分组成功情况中的最左边。也就是，r是所有成功分组情况中，组内人数最多的值里面最小的。
此外如果r没有动，那就说明根本就没有mid可以分组成功。
代码：
#include <iostream> #include<algorithm> #include<unordered_map> using namespace std; const int N=1e5+10; unordered_map<int,int> mp; int mr; int n; int m; bool check(int mid){//mid为人数最多的数量 if(mr<mid)return false; int res=0; for(auto it:mp){ if(it.second>mid){ res+=(it.second+mid-1)/mid;//向上取整 }else if(it.second<=mid){ res++; } } if(res>m)return false; return true; } int main() { cin>>n>>m; for(int i=1;i<=n;i++){ int x; cin>>x; mp[x]++; mr=max(mr,mp[x]); } int l=0,r=mr+1; while(l+1!=r){ int mid=(l+r)>>1; if(check(mid))r=mid; else l=mid; } if(r!=mr+1)cout<<r<<endl; else cout<<-1<<endl; return 0; }
3.拓扑排序
思路：拓扑排序的板子。先存一下边，再存一下每个点的入度。遍历每一条边，遍历的同时删除当前边，即入度减减。如果这个点的入度为0了，就入队列。拓扑排序保证，越早入队列的点，一定越在路径的前面。最后看一下是否每个点都入队列就行。
代码：
#include <iostream> #include<vector> #include<queue> using namespace std; const int N=2e5+10; int n,m; int d[N]; vector<int> ans; bool topu(vector<vector<int>>& g){ queue<int> q; for(int i=1;i<=n;i++){ if(d[i]==0){ ans.push_back(i); q.push(i); } } while(!q.empty()){ int t=q.front(); q.pop(); //cout<<t<<" kkk "; for(auto it:g[t]){ d[it]--; if(d[it]==0){ q.push(it); ans.push_back(it); } } } //cout<<ans.size()<<endl; if(ans.size()==n)return true; return false; } int main() { cin>>n>>m; vector<vector<int>> g(n+1); while(m--){ int a,b; cin>>a>>b; g[a].push_back(b); d[b]++; } if(!topu(g))cout<<-1<<endl; else { for(int i=0;i<ans.size();i++){ if(i!=ans.size()-1)cout<<ans[i]<<" "; else cout<<ans[i]; } } return 0; }
