【C++】 —— 笔试刷题day_15

刷题day_15，继承加油！！！
  一、平方数

标题剖析

   标题给出一个数，让我们找到离它近来的一个平方数，然后输出即可。
  算法思绪

这道题总体来说还优劣常简朴的。
这里先来看一种思绪，就是从1开始找，找到小于x的最大的平方数l和大于x的最小的平方数r；然后判断r-x和x-l中哪一个最小即可。
但是，主播主播你的这种思绪确实能办理标题，但照旧太贫苦了，有没有更加简朴易上手的方法；
有的兄弟有的，我们不妨来看看这种思绪：
   我们知道sqrt函数可以对一个数举行开根号预算，它会返回一个double范例是数据；
  那我们对这个返回值强转一下，转成整型不就拿到l，再对其加一就拿到了r。
  如许我们这个数是在区间[l*l , r*r]内的，我们判断r*r - x和x - l*l哪一个最小即可。
  

代码实现

1. #include<iostream>
2. #include<cmath>
4. using namespace std;
6. int main()
7. {
8.     long long x;
9.     cin>>x;
10.     long long a = sqrt(x);
11.     long long l = a*a, r = (a+1)*(a+1);
12.     if(x-l > r-x)
13.         cout<<r<<endl;
14.     else
15.         cout<<l<<endl;
16.     return 0;
17. }

复制代码

二、分组

标题剖析

   标题形貌：我们如今要对同砚们举行分组，每一个同砚都善于一个声部；我们要将善于同一个声部是同砚分到一个组（差别组的同砚可以善于同一个分部）；
  我们想要每一个组的同砚数目尽大概少，假如我们可以或许顺遂安排就输出 组中同砚数目最多的人数；否则输出-1。
  转换成底阿妈头脑就是：
   输入n,m，表现一共n个人，我们要分成m个组；其次的n个数，表现每一个同砚它善于的声调。
  算法思绪

那这道题，我们怎样去写呢？
初次看到这道题，博主有一种思绪：
   起首记载善于同一个音调的人的数目；
  然后将这些数目放入到堆中，我们先把善于同一个声调的同砚分到一个组；假如此时的组数要大于m就表现我们没办法顺遂分组，就输出1。
  然后我们堆中存放的就是每一组同砚的数目，取出来堆顶数据，然后将它分成两组，再放回到堆中。（这一个操纵可以明白为：每次将同砚数最多的组别分成两组）
  重复取出来堆顶数据，分成两组然后放回堆中，知道我们堆中的数据个数便是m；
  此时我们堆顶数据就是全部组中，同砚数目最多的组别的同砚数。
  但是，这里博主的想法是错误的，博主这里只是简朴记载一下自己当时的想法。
如今我们来看这道题的办理思绪：
   对于这道题，我们直接根据善于每一个声调的人数去找这些同砚要分成多少组，那肯定不实际的；
  假如我们善于一个声调的有k人，那我们就要分1，2，3... k组，k中环境，再算上其他组的各种环境，那可想而知有多贫苦了。
  既然，我们根据善于每一个声调的人数去找分成多少组不可，那我们就根据每一个组的人数，去找善于每一个声调的人可以分成多少组。
   假设我们如今每一个组中最多有x人，假设善于某一个声调的人数为y，那我们就可以将y分成y/x个组（留意，我们这里y不肯定能被x整除，假如不能整除，我们就要多分一个组）以是应该分成y/x + (y%x==0?0:1)个组。
  那我们记载了善于每一个声调的人数，那我们在求一下善于同一个声调可以或许分成多少组，求出来每个组有最多x个人时，必要多少组；
  我们求出的必要的组数sum，假如sum>m就阐明我们的x取小了，我们就要将x取的大一点再求必要的组数；
  如许直到sum<=m时，我们就找到了人数最多的小组人数最小的环境，然后返回即可。
  这里我们取x的值，从·1`开始，直到善于某个声调最多的人数，可以使用暴力摆列，但是如许大概会超时。
这里我们在细致分析一下：
   当我们x取小了，即sum > m时，我们就要取x大一点的数（在区间[x + 1 , hmax]中取）；假如x取大了，即sum < m，那我们就让x小一点，在区间[1 , x]中取；
  看到这里信任已经看出来怎样去优化了，那就是二分；
   在区间[1 , hmax]中，我们求出来的sum是递减的，那我们就可以使用二分去查找满意条件中最小的sum
  

代码实现

在实当代码之前，我们先来理清思绪（上面形貌一些乱）
   

• 起首我们要先统计善于每一种声调的人数，而且也要找到善于某一种声调人数的最大值hmax。
  
• 然后就是实现一个check函数，它用来判断使用x求出来的sum是否小于便是m。
  
• 在使用二分查找之前，先举行一下判断，假如cnt.size()>m就表现我们声调的种类大于要分的组数，那肯定不能完成使命；输出-1即可。
  
• 末了就是使用二分，然后去找到满意条件中最小的sum。
  

  这里二分：，当我们用x求出来的sum是小于便是m时，我们让right = mid，而不是mid - 1（由于大概前面求出来的sum是便是m的）。

1. #include<iostream>
2. #include<unordered_map>
3. using namespace std;
4. int n,m;
5. unordered_map<int,int> cnt;
7. bool check(int x)
8. {
9.     int sum = 0;
10.     for(auto& e:cnt)
11.     {
12.         sum +=(e.second/x + (e.second%x == 0?0:1));
13.     }
14.     return sum<=m;
15. }
16. int main()
17. {
18.     cin>>n>>m;
19.     int hmax = 0;
20.     for(int i=0;i<n;i++)
21.     {
22.         int x;
23.         cin>>x;
24.         cnt[x]++;
25.         if(cnt[x]>hmax)
26.             hmax = cnt[x];
27.     }
28.     if(cnt.size()>m)
29.         cout<<-1<<endl;
30.     //二分
31.     else
32.     {
33.         int left = 1, right = hmax;
34.         while(left<right)
35.         {
36.             int mid = (left+right)/2;
37.             if(check(mid))
38.                 right = mid;
39.             else
40.                 left = mid + 1;
41.         }
42.         cout<<left<<endl;
43.     }
44.     return 0;
45. }

复制代码

三、【模板】拓扑排序

标题剖析

   这道题没有任何弯弯绕绕，直接就观察拓扑排序，给我们一个包罗n条边的有向无环图，然我们输出该图的拓扑排序；
  **输入：**起首输入n、m表现点的个数和边的个数，然后m行输入两个整数v1,v2表现v1到v2之间有一条有向边。
  算法思绪

这里先简朴看一下我们怎样输出一个有向无环图的拓扑排序：
   起首在图中选择一个入度为0的节点，并输出该节点；
  然后将这个节点从图中删除，而且删除全部以该节点为顶点的有向边。
  重复操纵，摘到输出图中的全部节点。
  以图中示例来说：

那如今我们来看代码怎样去实现：
在上述形貌中，我们必要记载每一个有向边，还要记载每一个节点的入度，为了能实现拓扑排序，我们这里使用quque
   记载每一个有向边：vector<vector<int>>，下标表现每一个有向边的出发点，i位置的vector<int>表现从i位置到其他节点的有向边。
  记载每一个节点的入度：使用hash来记载即可。
  queue：这里queue的作用就是存放当前节点，然后举行删除当前节点和以当前节点开始的有向边，然后找到入度为0的节点放入queue中。
  记载结果：使用vector<int> ret来记载结果，假如末了ret中数据个数便是n就说存在拓扑排序，就输出；否则输出-1。
  代码实现

这里有应该坑，就是输出结果时，末了面不能有空格。

1. #include <iostream>
2. #include <queue>
3. #include <vector>
5. using namespace std;
7. int main() {
8.     int n, m;
9.     cin >> n >> m;
10.     vector<vector<int>> arr(n + 1);
11.     vector<int> hash(n + 1);
12.     for (int i = 0 ; i < m; i++) {
13.         int x, y;
14.         cin >> x >> y;
15.         hash[y]++;
16.         arr[x].push_back(y);
17.     }
18.     //找到度为0的节点
19.     queue<int> q;
20.     for (int i = 1; i <= n; i++) {
21.         if (hash[i] == 0)
22.             q.push(i);
23.     }
24.     vector<int> ret;//记录最终结果
25.     while (!q.empty()) {
26.         int x = q.front();
27.         q.pop();
28.         ret.push_back(x);
29.         //删除x节点和所有x开始的有向边
30.         for (auto& e : arr[x]) {
31.             hash[e]--;
32.             if (hash[e] == 0) {
33.                 q.push(e);
34.             }
35.         }
36.     }
37.     //输出结果
38.     //如果ret中数据个数等于n就说明存在拓扑排序
39.     //这里有一个坑:最后一个字符的后面不要输出空格
40.     if (ret.size() == n) {
41.         for (int i = 0; i < ret.size(); i++) {
42.             cout << ret[i];
43.             if (i < ret.size() - 1)
44.                 cout << ' ';
45.         }
46.     } else {
47.         cout << -1 << endl;
48.     }
49.     return 0;
50. }

复制代码

到这里本篇文章内容就竣事了
感谢各位的支持
我的博客即将同步至腾讯云开辟者社区，约请各人一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=2oul0hvapjsws