平方数

题目链接：平方数 (nowcoder.com)

思路：水题直接过。

AC code：

#include<iostream>
#include<cmath>
using namespace std;
int main()
{long long int n; cin >> n;long long int a = sqrtl(n);long long int b = a + 1;if( abs(n - a * a) > abs(n - b * b))cout << b * b;else cout << a * a;return 0;
}

分组

题目链接：E-分组_牛客小白月赛40 (nowcoder.com)

思路：

题目中要求人数最多的小组人尽量少，即可二分每个小组人数。

注意如果小组人数大于 最多人的那个最大值 是不可以的。

多关注下边界条件即可。

AC code：

#include<iostream>
#include<unordered_map>
#include<algorithm>
using namespace std;
unordered_map<int,int> mp;
int n,m;
int cnt;bool check(int x)
{int k = 0;//小组数for(auto it : mp){if(it.second > x)k +=(it.second + x - 1) / x;//向上取整elsek ++;}if(k > m) return 0;return 1;
}int main()
{cin >> n >> m;int maxx = -2e9;for(int i = 0; i < n; i ++){int x; cin >> x;mp[x]++;maxx = max(maxx, mp[x]);}int l = 0, r = 1e5 + 10; // 二分小组人数while(l < r){int mid = l + r >> 1;if(check(mid)) r = mid;else l = mid + 1;}if(r <= maxx)cout << r << endl;else cout << -1 << endl;return 0;
}

AB13 【模板】拓扑排序

题目链接：【模板】拓扑排序_牛客题霸_牛客网 (nowcoder.com)

思路：

模板题 根据入度是否为零 依次入队即可。

AC code：

#include<iostream>
#include<cstring>
using namespace std;const int N = 100010;int h[N], e[N], ne[N], idx;int q[N], d[N]; // d[N] 入度int n, m;void add(int a, int b) {e[idx] = b;ne[idx] = h[a];h[a] = idx ++;
}
void topsort() {int hh = 0, tt = -1;for (int i = 1; i <= n; i++)if (d[i] == 0) q[++tt] = i;while (hh <= tt) {int a = q[hh++];for (int i = h[a]; i != -1; i = ne[i]) {int j = e[i];d[j]-- ;if (!d[j]) q[++tt] = j;}}if (tt == n - 1)for (int i = 0; i < n; i++) cout << q[i] << " ";elsecout << -1;}
int main() {memset(h, -1, sizeof(h));cin >> n >> m;for (int i = 1; i <= m; i++) {int a, b;cin >> a >> b;add(a, b);d[b]++;}topsort();return 0;
}