Day 27kotori 和氣球解題思路放置第一個(gè)位置有 n 種方法第二個(gè)位置就有 n-1 種第三個(gè)位置也有 n-1 種代碼實(shí)現(xiàn)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 擴(kuò)散方向當(dāng)前坐標(biāo)被誰先擴(kuò)散誰就決定當(dāng)前坐標(biāo)的最小距離在擴(kuò)散前先計(jì)算擴(kuò)散坐標(biāo)的最小距離擴(kuò)散后標(biāo)記該坐標(biāo)為已擴(kuò)散代碼實(shí)現(xiàn)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});// 起點(diǎn)距離為 0distance[x0][y0]0;check[x0][y0]true;while(!queue.isEmpty()){int[]pointqueue.poll();intcurxpoint[0],curypoint[1];// 枚舉四個(gè)方向for(int[]p:d){intxcurxp[0];intycuryp[1];// 注意棋盤邊界if(x1||xn||y1||ym)continue;if(check[x][y])continue;if(grids[x][y]*)continue;// 四個(gè)方向, 在入隊(duì)列前, 就可以算出其距離// 因?yàn)? 首先這個(gè)點(diǎn)能被擴(kuò)散到, 其次, 這個(gè)點(diǎn)最先被誰擴(kuò)散, 誰就決定其最小距離distance[x][y]distance[curx][cury]1;if(xx1yy1){System.out.println(distance[x][y]);return;}queue.offer(newint[]{x,y});// 標(biāo)記為已擴(kuò)散check[x][y]true;}}// 隊(duì)列為空, 都還沒計(jì)算出終點(diǎn), 說明到達(dá)不了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());}}主持人調(diào)度 (二)解題思路使用優(yōu)先級隊(duì)列存儲(chǔ)活動(dòng)結(jié)束時(shí)間當(dāng)前獲取的開始時(shí)間如果早于最早活動(dòng)結(jié)束時(shí)間說明活動(dòng)沖突新增加一個(gè)主持人如果不沖突就復(fù)用主持人然后把最早結(jié)束活動(dòng)出隊(duì)列注意題目中的例子一定要使用Integer.compare(v1[0], v2[0])來避免比較過程計(jì)算溢出排序錯(cuò)誤代碼實(shí)現(xiàn)importjava.util.*;publicclassSolution{publicintminmumNumberOfHost(intn,int[][]startEnd){// 當(dāng)開始時(shí)間分別接近 Integer.MAX_VALUE 和 Integer.MIN_VALUE 時(shí)減法會(huì)發(fā)生整數(shù)溢出導(dǎo)致排序順序錯(cuò)誤。并且兩個(gè)開始時(shí)間相等時(shí)原比較器仍返回 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;}}