笔试强训 Day 27：kotori 和气球、走迷宫、主持人调度 (二)
)
Day 27
kotori 和气球
解题思路：
- 放置第一个位置有 n 种方法，第二个位置就有 n-1 种，第三个位置也有 n-1 种
代码实现：
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);}}走迷宫
解题思路：
- 参考腐烂的橘子，使用 bfs ，扩散方向；
- 当前坐标被谁先扩散，谁就决定当前坐标的最小距离；
- 在扩散前，先计算扩散坐标的最小距离，扩散后，标记该坐标为已扩散；
代码实现：
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());}}主持人调度 (二)
解题思路：
- 使用优先级队列，存储活动结束时间；
- 当前获取的开始时间，如果早于最早活动结束时间，说明活动冲突，新增加一个主持人；
- 如果不冲突，就复用主持人，然后把最早结束活动出队列；
- 注意，题目中的例子，一定要使用
Integer.compare(v1[0], v2[0])来避免比较过程计算溢出，排序错误
代码实现：
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;}}