【强训笔记】day15

2024-05-08 23:20

文章标签 笔记强训 day15

本文主要是介绍【强训笔记】day15，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

NO.1
在这里插入图片描述
代码实现：

#include<iostream>
#include<cmath>using namespace std;
typedef long long ll;int main()
{ll x;cin>>x;ll a=sqrt(x);ll x1=a*a,x2=(a+1)*(a+1);if(x-x1<x2-x) cout<<x1<<endl;else cout<<x2<<endl;return 0;
}

NO.2
在这里插入图片描述
思路：暴力枚举。哈希表先统计各个声部的种类的人数并且知道最多人数是多少，如果种类多于我们要分的组数，那么直接输出-1，否则从1开始到最大人数遍历直到实现分组实现所分的组数小于m，分组的时候，让人数除以遍历的i，如果有余数就多分一组。

代码实现：

#include<iostream>
#include <unordered_map>using namespace std;unordered_map<int, int> cnt;
int n,m;bool check(int x)
{int g=0;for(auto& [a,b]:cnt){g+=b/x+(b%x==0?0:1);}return g<=m;
}
int main()
{cin>>n>>m;int hmax=0;for(int i=0;i<n;i++){int x;cin>>x;hmax=max(hmax,++cnt[x]);}int kinds=cnt.size();if(kinds>m) cout<<-1<<endl;else{for(int i=1;i<hmax;i++){if(check(i)){cout<<i<<endl;break;}}}return 0;
}

二分法优化代码：中间位置比较特殊，中间位置左边都是大于m组的，左边都是小于等于m组的。

#include<iostream>
#include <unordered_map>using namespace std;unordered_map<int, int> cnt;
int n,m;bool check(int x)
{int g=0;for(auto& [a,b]:cnt){g+=b/x+(b%x==0?0:1);}return g<=m;
}
int main()
{cin>>n>>m;int hmax=0;for(int i=0;i<n;i++){int x;cin>>x;hmax=max(hmax,++cnt[x]);}int kinds=cnt.size();if(kinds>m) cout<<-1<<endl;else{int l=1,r=hmax;while(l<r){int mid=(l+r)/2;if(check(mid)) r=mid;else l=mid+1;}cout<<l<<endl;   }return 0;
}

NO.3
在这里插入图片描述

代码实现：

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int N = 2e5 + 10;
vector<vector<int>> edges(N); // edges[i] 表⽰ i 这个点所连接的边的信息
int in[N]; // 统计⼊度信息
int n, m;
queue<int> q;
vector<int> ret; // 记录最终结果
int main()
{cin >> n >> m;while (m--){int a, b;cin >> a >> b;edges[a].push_back(b); // 存储边的信息in[b]++; // 存储⼊度}for (int i = 1; i <= n; i++) // 把⼊度为 0 的点放进队列中{if (in[i] == 0){q.push(i);}}while (q.size()){int a = q.front();q.pop();ret.push_back(a);for (auto b : edges[a]){if (--in[b] == 0){q.push(b);}}}// 判断if (ret.size() == n){for (int i = 0; i < n - 1; i++){cout << ret[i] << " ";}cout << ret[n - 1]; // 测评会考虑最后⼀个元素的空格}else{cout << -1 << endl;}return 0;
}