笔试强训 Day 27：kotori 和气球、走迷宫、主持人调度 (二)

Day 27

kotori 和气球

解题思路：

代码实现：

importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){Scannerin=newScanner(System.in);intn=in.nextInt(),m=in.nextInt();longret=n;for(inti=2;i<=m;i++){ret=ret*(n-1)%109;}System.out.println(ret);}}

走迷宫

解题思路：

代码实现：

importjava.util.*;importjava.io.*;publicclassMain{privatestaticReadin=newRead();publicstaticvoidmain(String[]args)throwsIOException{intn=in.nextInt(),m=in.nextInt();intx0=in.nextInt(),y0=in.nextInt();intx1=in.nextInt(),y1=in.nextInt();char[][]grids=newchar[n+2][m+2];for(inti=1;i<=n;i++){Stringline=in.next();for(intj=1;j<=m;j++){grids[i][j]=line.charAt(j-1);}}if(grids[x0][y0]=='*'||grids[x1][y1]=='*'){System.out.println(-1);return;}int[][]d=newint[][]{{-1,0},{1,0},{0,1},{0,-1}};boolean[][]check=newboolean[n+2][m+2];int[][]distance=newint[n+2][m+2];Queue<int[]>queue=newLinkedList<>();queue.offer(newint[]{x0,y0});// 起点距离为 0distance[x0][y0]=0;check[x0][y0]=true;while(!queue.isEmpty()){int[]point=queue.poll();intcurx=point[0],cury=point[1];// 枚举四个方向for(int[]p:d){intx=curx+p[0];inty=cury+p[1];// 注意棋盘边界if(x<1||x>n||y<1||y>m)continue;if(check[x][y])continue;if(grids[x][y]=='*')continue;// 四个方向, 在入队列前, 就可以算出其距离// 因为, 首先这个点能被扩散到, 其次, 这个点最先被谁扩散, 谁就决定其最小距离distance[x][y]=distance[curx][cury]+1;if(x==x1&&y==y1){System.out.println(distance[x][y]);return;}queue.offer(newint[]{x,y});// 标记为已扩散check[x][y]=true;}}// 队列为空, 都还没计算出终点, 说明到达不了System.out.println(-1);}}classRead{StringTokenizerst=newStringTokenizer("");BufferedReaderbf=newBufferedReader(newInputStreamReader(System.in));Stringnext()throwsIOException{if(!st.hasMoreTokens()){Stringline=bf.readLine();if(line==null)returnnull;st=newStringTokenizer(line);}returnst.nextToken();}intnextInt()throwsIOException{returnInteger.parseInt(next());}}

主持人调度 (二)

解题思路：

代码实现：

importjava.util.*;publicclassSolution{publicintminmumNumberOfHost(intn,int[][]startEnd){// 当开始时间分别接近 Integer.MAX_VALUE 和 Integer.MIN_VALUE 时，减法会发生整数溢出，导致排序顺序错误。并且两个开始时间相等时，原比较器仍返回 1，也违反了比较器约定。Arrays.sort(startEnd,(v1,v2)->Integer.compare(v1[0],v2[0]));PriorityQueue<Integer>queue=newPriorityQueue<>();intcnt=1;for(inti=0;i<n;i++){if(queue.isEmpty()){queue.offer(startEnd[i][1]);}else{intpe=queue.peek();intns=startEnd[i][0];if(ns<pe){cnt++;}else{queue.poll();}queue.add(startEnd[i][1]);}}returncnt;}}