笔试强训 Day 27：kotori 和气球、走迷宫、主持人调度 (二)
)
Day 27kotori 和气球解题思路放置第一个位置有 n 种方法第二个位置就有 n-1 种第三个位置也有 n-1 种代码实现importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){ScannerinnewScanner(System.in);intnin.nextInt(),min.nextInt();longretn;for(inti2;im;i){retret*(n-1)%109;}System.out.println(ret);}}走迷宫解题思路参考腐烂的橘子使用 bfs 扩散方向当前坐标被谁先扩散谁就决定当前坐标的最小距离在扩散前先计算扩散坐标的最小距离扩散后标记该坐标为已扩散代码实现importjava.util.*;importjava.io.*;publicclassMain{privatestaticReadinnewRead();publicstaticvoidmain(String[]args)throwsIOException{intnin.nextInt(),min.nextInt();intx0in.nextInt(),y0in.nextInt();intx1in.nextInt(),y1in.nextInt();char[][]gridsnewchar[n2][m2];for(inti1;in;i){Stringlinein.next();for(intj1;jm;j){grids[i][j]line.charAt(j-1);}}if(grids[x0][y0]*||grids[x1][y1]*){System.out.println(-1);return;}int[][]dnewint[][]{{-1,0},{1,0},{0,1},{0,-1}};boolean[][]checknewboolean[n2][m2];int[][]distancenewint[n2][m2];Queueint[]queuenewLinkedList();queue.offer(newint[]{x0,y0});// 起点距离为 0distance[x0][y0]0;check[x0][y0]true;while(!queue.isEmpty()){int[]pointqueue.poll();intcurxpoint[0],curypoint[1];// 枚举四个方向for(int[]p:d){intxcurxp[0];intycuryp[1];// 注意棋盘边界if(x1||xn||y1||ym)continue;if(check[x][y])continue;if(grids[x][y]*)continue;// 四个方向, 在入队列前, 就可以算出其距离// 因为, 首先这个点能被扩散到, 其次, 这个点最先被谁扩散, 谁就决定其最小距离distance[x][y]distance[curx][cury]1;if(xx1yy1){System.out.println(distance[x][y]);return;}queue.offer(newint[]{x,y});// 标记为已扩散check[x][y]true;}}// 队列为空, 都还没计算出终点, 说明到达不了System.out.println(-1);}}classRead{StringTokenizerstnewStringTokenizer();BufferedReaderbfnewBufferedReader(newInputStreamReader(System.in));Stringnext()throwsIOException{if(!st.hasMoreTokens()){Stringlinebf.readLine();if(linenull)returnnull;stnewStringTokenizer(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]));PriorityQueueIntegerqueuenewPriorityQueue();intcnt1;for(inti0;in;i){if(queue.isEmpty()){queue.offer(startEnd[i][1]);}else{intpequeue.peek();intnsstartEnd[i][0];if(nspe){cnt;}else{queue.poll();}queue.add(startEnd[i][1]);}}returncnt;}}
