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());}}注意一个小细节：next()方法最好用while，不要只用if。因为输入里可能有空行，用while更稳。