建筑行业平台,seo优化包括什么,天津业之峰装饰公司官网,巢湖seo推广选哪家题目部分
题目乘坐保密电梯难度难题目说明难 有一座保密大楼#xff0c;你从 0 楼到达指定楼层 m#xff0c;必须这样的规则乘坐电梯#xff1a; 给定一个数字序列#xff0c;每次根据序列中的数字 n,上升 n 层或者下降 n 层#xff0c;前后两次的方向必须相反#xff0…题目部分
题目乘坐保密电梯难度难题目说明难 有一座保密大楼你从 0 楼到达指定楼层 m必须这样的规则乘坐电梯 给定一个数字序列每次根据序列中的数字 n,上升 n 层或者下降 n 层前后两次的方向必须相反规定首次的方向向上自行组织序列的顺序按规定操作到达指定楼层。 求解到达楼层的序列组合如果不能到达楼层给出小于该楼层的最近序列组合。 说明 1. 操作楼层不限定楼层范围楼层可以为负数。 2. 必须对序列中的每个项进行操作不能只使用一部分。 3. 无论是上楼还是下楼优先使用序列中尚未使用过的最大数字。输入描述第一行期望的楼层取值范围 [1,50]序列总个数取值范围 [1,23]。 第二行序列每个值的取值范围 [1,50]。输出描述能够到达楼层或者小于该楼层最近的序列。补充说明1. 操作楼层时不限定楼层范围。 2.必须对序列中的每个数操作不能只使用一部分。 3.无论是上楼还是下楼优先使用序列中未使用过的最大数字。------------------------------------------------------示例示例1输入5 3 1 2 6输出6 2 1说明1 2 6 和 6 2 1 均为可行解按照先处理大值的规则输出结果为 6 2 1。 解读与分析
题目解读
初始值为 0 给定一个最终值设为 finalValue和一序列的数字让这一系列的数字经过“特定规则”进行加减之后最后的值为 finalValue。特定的规则是 1. 把数字按照自定义的规则排序其中下标为偶数的数字按照降序排列下标为奇数的数字也按照降序排列。即第 1 个数字 大于第 3 个数字第 3 个数字大于第 5 个数字……第 2 个数字大于第 4 个数字第 4 个数字大于第 6 个数字…… 2. 第 1 个数字减去第 2 个数字加上第 3 个数字减去第 4 个数字加上第 5 个数字……当所有的数字都用完之后值等于 finalValue。 3. 按照规则 1 和规则 2 执行完毕后所有的数字都会使用且仅使用一次。 4. 如果无论怎样排序最后都不可能等于 finalValue那就把 finalValue 改成小于 finalValue 并且能达到的最大值在此条件下输出数字的排序。
分析与思路
假设此题中一序列数字的长度为 n数字放在 intArr 中最终的值为 finalValue。 当最终能达到 finalValue 时我们看到所有做加法的数字之和与所有做减法的数字的数字之和相差 finalValue。假设数组所数字之和为 sumArr 所有数字之和加上 finalValue设为 sum。那么所有所有做加法的数字之和为 sum / 2所有做减法的数字之和加上 finalValue也等于 sum/2 。因为加法和减法是交替的这意味着当 n 为奇数时做加法的数字个数为 ( n/2 1 )做减法的数字个数为 ( n/2 )当 n 为偶数时做加法和做减法的数字个数均为 (n/2)。 这样此题可以理解成从 n 个数字中 找出 n/2 1 个数n 为奇数时或 n /2 个数n 为偶数时使其和等于 sum/2。 刚才提到的是最终能达到 finalValue 的情况实际可能无法达到 finalValue那么题目就变成了从 n 个数字中 找出 n/2 1 个数n 为奇数时或 n /2 个数n 为偶数时使其和为不大于 sum/2的最大数字。 那么怎样找到这些数字呢我们可以先对数字从大到小排序然后才去穷举的方式找到它们找到之后剩下的就是输出数字。 在输出数字时在数字的顺序中奇数位必须是降序排列偶数位也必须是降序排列。那么在输出 n/2 1 或 n/2 时使其从大到小排序剩下的数字也是从大到小排序。 代码实现
Java代码
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.ArrayList;
import java.util.Scanner;/*** 乘坐保密电梯* * since 2023.11.28* version 0.1* author Frank**/
public class SecretLift {public static void main(String[] args) {Scanner sc new Scanner(System.in);while (sc.hasNext()) {String input sc.nextLine();String[] inputArr input.split( );int finalValue Integer.parseInt(inputArr[0]);int numberCnt Integer.parseInt(inputArr[1]);input sc.nextLine();inputArr input.split( );Integer[] numbers new Integer[numberCnt];for (int i 0; i numberCnt; i) {numbers[i] Integer.parseInt(inputArr[i]);}processSecretLift(finalValue, numbers);}}private static void processSecretLift(int finalValue, Integer[] numbers) {Arrays.sort(numbers, new ComparatorInteger() {public int compare(Integer o1, Integer o2) {return o2 - o1;}});int sum getSum(finalValue, numbers);int m numbers.length / 2;if (numbers.length % 2 1) {m 1;}int target sum / 2; // 不需要关心是否整除因为无法整除意味着无法到达。List plusValues new ArrayListInteger();List numberList new ArrayListInteger();for (int i 0; i numbers.length; i) {numberList.add(numbers[i]);}getPlusValues(plusValues, 0, m, target, numberList);ListInteger finalList getMergedList(plusValues, numberList);StringBuffer sb new StringBuffer();for (int i 0; i finalList.size(); i) {sb.append(finalList.get(i));if (i ! finalList.size() - 1) {sb.append( );}}System.out.println(sb.toString());}private static int getSum(int finalValue, Integer[] numbers) {int ret finalValue;for (int i 0; i numbers.length; i) {ret numbers[i];}return ret;}private static int getPlusValues(ListInteger plusValues, int curSum, int m, int target,ListInteger numberList) {if (plusValues.size() m curSum target) {return curSum;}int tmpSum -1;List bestPlusValues new ArrayListInteger();List numberList4Best new ArrayListInteger();for (int i 0; i numberList.size(); i) {int tmpNumber numberList.get(i);if (curSum tmpNumber target) {continue;}plusValues.add(tmpNumber);numberList.remove(i);int tmp getPlusValues(plusValues, curSum tmpNumber, m, target, numberList);if (tmp -1) {plusValues.remove(plusValues.size() - 1);numberList.add(i, tmpNumber);continue;}if (tmp target) {return target;} else if (tmp tmpSum tmp target) {tmpSum tmp;copyList(bestPlusValues, plusValues);copyList(numberList4Best, numberList);}plusValues.remove(plusValues.size() - 1);numberList.add(i, tmpNumber);}if (tmpSum -1) {return -1;}copyList(plusValues, bestPlusValues);copyList(numberList, numberList4Best);return tmpSum;}public static void copyList(ListInteger target, ListInteger source) {target.clear();target.addAll(source);}public static List getMergedList(ListInteger plusValues, ListInteger numberList) {ListInteger ret new ArrayListInteger();for (int i 0; i plusValues.size(); i) {ret.add(plusValues.get(i));if (i numberList.size()) {ret.add(numberList.get(i));}}return ret;}
} JavaScript代码
const rl require(readline).createInterface({ input: process.stdin });
var iter rl[Symbol.asyncIterator]();
const readline async () (await iter.next()).value;
void async function() {while (line await readline()) {var inputArr line.split( );var finalValue parseInt(inputArr[0]);var numberCnt parseInt(inputArr[1]);line await readline()inputArr line.split( );var numbers new Array();for (var i 0; i numberCnt; i) {numbers[i] parseInt(inputArr[i]);}processSecretLift(finalValue, numbers);}
}();function processSecretLift(finalValue, numbers) {numbers.sort(function(a, b) {return b - a;});var sum getSum(finalValue, numbers);var m parseInt(numbers.length / 2);if (numbers.length % 2 1) {m 1;}var target parseInt(sum / 2); // 不需要关心是否整除因为无法整除意味着无法到达。var plusValues new Array();var numberList new Array();for (var i 0; i numbers.length; i) {numberList.push(numbers[i]);}getPlusValues(plusValues, 0, m, target, numberList);var finalList getMergedList(plusValues, numberList);var retStr ;for (var i 0; i finalList.length; i) {retStr finalList[i];if (i ! finalList.length - 1) {retStr ;}}console.log(retStr);
}function getSum(finalValue, numbers) {var ret finalValue;for (var i 0; i numbers.length; i) {ret numbers[i];}return ret;
}function getPlusValues(plusValues, curSum, m, target, numberList) {if (plusValues.length m curSum target) {return curSum;}var tmpSum -1;var bestPlusValues new Array();var numberList4Best new Array();for (var i 0; i numberList.length; i) {var tmpNumber numberList[i];if (curSum tmpNumber target) {continue;}plusValues.push(tmpNumber);numberList.splice(i, 1);var tmp getPlusValues(plusValues, curSum tmpNumber, m, target, numberList);if (tmp -1) {plusValues.pop();numberList.splice(i, 0, tmpNumber);continue;}if (tmp target) {return target;} else if (tmp tmpSum tmp target) {tmpSum tmp;copyList(bestPlusValues, plusValues);copyList(numberList4Best, numberList);}plusValues.pop();numberList.splice(i, 0, tmpNumber);}if (tmpSum -1) {return -1;}copyList(plusValues, bestPlusValues);copyList(numberList, numberList4Best);return tmpSum;
}function copyList(target, source) {target.splice(0, target.length);for (var i 0; i source.length; i) {target.push(source[i]);}
}function getMergedList(plusValues, numberList) {var ret new Array();for (var i 0; i plusValues.length; i) {ret.push(plusValues[i]);if (i numberList.length) {ret.push(numberList[i]);}}return ret;
} (完)
