当前位置：首页 > news >正文

笔试强训 Day 15：平方数 + 分组 + 拓扑排序

news 2026/6/29 17:59:29

Day 15

平方数

方法一：循环

把循环条件从遍历所有i，只循环到i * i >= n为止：

importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);longn=sc.nextLong();longx=0,y=0;for(longi=1;;i++){if(i*i>=n){x=i;y=i-1;break;}}longret=x*x;if(n-y*y<x*x-n){ret=y*y;}System.out.println(ret);}}

方法二：使用 Math.sqrt()

直接用平方根即可：

importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);longx=sc.nextLong();longa=(long)Math.sqrt(x);longy1=a*a;longy2=(a+1)*(a+1);if(x-y1<=y2-x){System.out.println(y1);}else{System.out.println(y2);}}}

分组

思路：

分组 + 二分查找；
题目很长，把题目有效信息复制到代码注释中；

解题步骤：

先统计种类，以及各个种类的数量；
分成 m 组，当种类都大于 m ，说明分不了，直接返回 -1；
种类小于 m，接下来就是要枚举最大人数；
使用二分查找，枚举最大人数，这个最大人数采纳，分出来的组要最临近但是小于 m 组；这个思路枚举出的最大值，是所有合法最大值中的最小值；

importjava.util.*;// 每一组里的同学都必须擅长同一个声部// 不同组同学擅长同一个声部的情况是可以出现的// 不希望出现任何一组的人过多// 人数最多的小组的人尽可能少// 输出一个数，表示人数最多的小组的人数// 无法顺利安排，请输出-1// n个数,a[i](1≤a[i]≤n)表示第i个学生的擅长声部publicclassMain{staticintm=0,n=0;staticint[]cnt;publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);n=sc.nextInt();m=sc.nextInt();intkind=0;cnt=newint[n+1];// 只输入 n 个数, 每个数 a[i] <= n, 记录每个数出现的次数for(inti=0;i<n;i++){intx=sc.nextInt();cnt[x]++;if(cnt[x]==1)kind++;}// 当种类大于分组数量, 无法安排if(kind>m){System.out.println(-1);return;}// 二分查找分组后人数的最大值, 人数范围 (1~k), 在能分成 m 组的最大值中, 找最小值intl=1,r=n,minmax=n;while(l<=r){intmid=(l+r)/2;if(check(mid)){minmax=mid;r=mid-1;}else{l=mid+1;}}System.out.println(minmax);}privatestaticbooleancheck(intk){// 此时 kind >= m, 一定可以分成 m 组, 因此需要枚举能分成 m 组时, 组最大值的最小值// 如果最大值是 k , 会分成 nead 组, nead 组必须在 m 内longneed=0;for(inti=1;i<=n;i++){if(cnt[i]>0){// 向上取整// cnt[2] = 3, k = 2, 可以分为 (3 + 2 - 1)/2 组// cnt[2] = 4, k = 2, 可以分为 (4 + 2 - 1)/2 组need+=(cnt[i]+k-1)/k;}}returnneed<=m;}}

相关题目推荐：爱吃香蕉的珂珂

拓扑排序

思路用Kahn 算法：

用邻接表存图，同时统计每个点的入度indegree。
把所有入度为0的点加入队列。
每次从队列取出一个点，加入拓扑序结果。
遍历它指向的所有点，将这些点的入度减一。
如果某个点入度变成0，就加入队列。
最后如果结果数量等于n，说明存在拓扑序；否则说明图中有环，输出-1。

基于你的代码可以这样写：

importjava.util.*;importjava.io.*;publicclassMain{privatestaticReadin=newRead();privatestaticPrintWriterout=newPrintWriter(newBufferedWriter(newOutputStreamWriter(System.out)));publicstaticvoidmain(String[]args)throwsIOException{intn=in.nextInt(),m=in.nextInt();List<Integer>[]graph=newArrayList[n+1];for(inti=1;i<=n;i++){graph[i]=newArrayList<>();}int[]indegree=newint[n+1];for(inti=0;i<m;i++){intu=in.nextInt();intv=in.nextInt();graph[u].add(v);indegree[v]++;}Queue<Integer>queue=newArrayDeque<>();for(inti=1;i<=n;i++){if(indegree[i]==0){queue.offer(i);}}int[]ans=newint[n];intidx=0;while(!queue.isEmpty()){intcur=queue.poll();ans[idx++]=cur;for(intnext:graph[cur]){indegree[next]--;if(indegree[next]==0){queue.offer(next);}}}if(idx!=n){out.println(-1);}else{for(inti=0;i<n;i++){if(i>0)out.print(" ");out.print(ans[i]);}out.println();}out.close();}}classRead{StringTokenizerst=newStringTokenizer("");BufferedReaderbf=newBufferedReader(newInputStreamReader(System.in));Stringnext()throwsIOException{while(!st.hasMoreTokens()){Stringline=bf.readLine();if(line==null)returnnull;st=newStringTokenizer(line);}returnst.nextToken();}intnextInt()throwsIOException{returnInteger.parseInt(next());}}