題目

獨立實現

基本思路

1、首先把題目給出的啟動機器初始化成數組,
2、用for循環模擬每隔1s更新這個初始化數組的前后兩個機器. (源碼中的updateTimeCount函數)
3、for循環每次循環后會檢查當前啟動機器列表是否全部啟動(源碼中的chechList函數)并保存當前的啟動機器列表(preStartMachineList)
4、如果機器沒有全部啟動 重復 2 - 3 流程
5、如果機器全部啟動了 拿preStartMachineList中保存的值去和0 - n-1的數組做差值比較,那么這個差值肯定就是最后啟動的機器列表

代碼實現

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();const readline = async () => (await iter.next()).value;void (async function () {// 保存總數和啟動數const [allCount, startCount] = (await readline()).split(" ");// Write your code herelet inputIndex = 0;// 記錄發動機啟動時間和序號的列表let machineInfo = [];while (inputIndex < Number(startCount)) {const inputLine = await readline();const [startTime, startIndex] = inputLine.split(" ");if (!machineInfo[startTime]) {machineInfo[startTime] = [];}machineInfo[startTime].push([startIndex]);inputIndex++;}machineInfo.filter((item) => item);// 用來保存全部啟動之前的機器列表 和全部啟動之后的機器列表之差就是最后啟動的機器數let preStartMachineList = [];// console.log("machineInfo", machineInfo);const updateTimeCount = (currentIndex) => {// console.log("resultList", JSON.stringify(resultList));resultList.forEach((result) => {// 小于當前時間戳,需要更新時間if (result && result.timeCount < currentIndex) {const steps = currentIndex - result.timeCount;result.startMachine = result.startMachine.map((item) => {const centerNumber = item[Math.floor(item.length / 2)];return [centerNumber - steps < 0? allCount - Math.abs(centerNumber - steps): centerNumber - steps,...item,centerNumber + steps >= allCount? 0 + Math.abs(allCount - (centerNumber + steps)): centerNumber + steps,];});// result.timeCount = currentIndex;}});// console.log("updateTimeCount", resultList?.[0]?.startMachine);};const chechList = (list) => {const startedMachine = Array.from(new Set(list.map((item) => item.startMachine).flat(Number.MAX_SAFE_INTEGER)));// console.log("checklist", startedMachine);if (startedMachine.length >= allCount) {return true;} else {preStartMachineList = startedMachine;return false;}};const resultList = [];// console.log("machineInfo", machineInfo);for (let i = 0; i < allCount; i++) {if (machineInfo[i]) {resultList.push({timeCount: i,startMachine: machineInfo[i].map((item) => [Number(item)]),});}updateTimeCount(i);// 全部啟動完成 后續循環跳過if (chechList(resultList)) {// console.log("finish", preStartMachineList);const lastStartMachineList = [];for (let j = 0; j < allCount; j++) {if (!preStartMachineList.includes(j)) {lastStartMachineList.push(j);}}console.log(lastStartMachineList.length);console.log(lastStartMachineList.join(" "));break;}}
})();

其他答案

實現思路

1、初始化一個項數為n的數組 初始化為無限大,表示機器的啟動時間
2、通過兩次遍歷找出所有機器的啟動時間 以0 2 0 6為例
3、最后得出的數組為[2,1,0,1,2,1,0,1]
3、最大的數就是最晚啟動時間,輸出最大數的個數以及index即可

代碼實現

	const rl = require("readline").createInterface({ input: process.stdin });var iter = rl[Symbol.asyncIterator]();const readline = async () => (await iter.next()).value;void (async function () {//   保存總發動機數量和首次啟動的發動機數量const [allCount, startCount] = (await readline()).split(" ").map(Number); // allCount = 8; startCount = 2const startTimeList = new Array(allCount).fill(Number.MAX_SAFE_INTEGER); // 初始化一個機器啟動時間數組 這個數組有8項 [最大值,最大值,最大值....] 因為最開始的啟動時間是未知的,所以這里我們初始化為最大值,表示機器啟動需要無限大時間let inputIndex = 0;do {// 在這里讀取機器啟動時間,比如0,2 表示機器2在第0秒啟動const [startTime, startIndex] = (await readline()).split(" ").map(Number);startTimeList[startIndex] = startTime;inputIndex++;} while (inputIndex < startCount);//  所以經過讀取輸入(0,2) (0,6)之后的startTimeList為[最大值,最大值,0,最大值,最大值,最大值,0,最大值]//   1、這里植入下對環數據結構最小啟動時間的理解,可以看到第2號機器和第6號機器都是從0秒啟動//   2、從第5號(實際上從任何機器開始都可以,隨便舉的🌰)機器的啟動時間開始分析,0 1 2 3 4 5 6 7//   3、因為是環形結構,所以機器的啟動時間實際就看和首批機器啟動時間的絕對值取小值就行了 比如第5號機器距離2號機器 有兩種方向 2 3 4 5需要3秒時間(5-2) 另一種走法需要2 1 0 7 6 5 需要5秒時間8-(5-2) 所以最終取到的是3和5之間的小值3秒//   4、但是因為6號機器也是第0秒啟動 所以5號機器從6號機器出發的路徑是 6 5 方向1需要6 5 1s(6-5)方向2 6 7 0 1 2 3 4 5 需要7秒(8-(6-5)) 取小值 1s//   5、綜上取到的5號機器的實際啟動時間是1s和3秒之間的小值 所以5號機器最終的啟動時間是1s.// 按照這個方法類推,可以推出所有機器的啟動時間for(let i=0;i<allCount;i++){for(let j=0;j<allCount;j++){// 方向1需要的啟動時間const direction_left = Math.abs(j - i)// 方向2需要的啟動時間const direction_right = allCount - Math.abs(j - i)// 取小值const minDistance = Math.min(direction_left, direction_right)startTimeList[i] = Math.min(startTimeList[i], startTimeList[j] + minDistance)}}const maxDistance = Math.max(...startTimeList)const resultList = []startTimeList.forEach((item, index) => {if(item === maxDistance) resultList.push(index)})console.log(resultList.length)console.log(resultList.join(' '))})();