企业官网建设流程全解析

台州做网站的电话,wordpress破解防盗链,国家高新技术企业名录,没有网站流量怎么办一、题目描述一支N个士兵的军队正在趁夜色逃亡#xff0c;途中遇到一条湍急的大河。 敌军在T的时长后到达河面#xff0c;没到过对岸的士兵都会被消灭。 现在军队只找到了1只小船#xff0c;这船最多能同时坐上2个士兵。当1个士兵划船过河#xff0c;用时为 a[i]#xff1…一、题目描述一支N个士兵的军队正在趁夜色逃亡途中遇到一条湍急的大河。敌军在T的时长后到达河面没到过对岸的士兵都会被消灭。现在军队只找到了1只小船这船最多能同时坐上2个士兵。当1个士兵划船过河用时为 a[i]0 i N当2个士兵坐船同时划船过河时用时为max(a[j],a[i])两士兵中用时最长的。当2个士兵坐船1个士兵划船时用时为 a[i]*10a[i]为划船士兵用时。如果士兵下河游泳则会被湍急水流直接带走算作死亡。请帮忙给出一种解决方案保证存活的士兵最多且过河用时最短。二、输入输出描述输入描述第一行N 表示士兵数(0N1,000,000)第二行T 表示敌军到达时长(0 T 100,000,000)第三行a[0] a[1] … a[i]… a[N- 1]a[i]表示每个士兵的过河时长(10 a[i] 100; 0 i N输出描述两个整数最多存活士兵数和最短用时用空格分隔。备注1两个士兵的同时划船时如果划速不同则会导致船原地转圈圈所以为保持两个士兵划速相同则需要向划的慢的士兵看齐。2两个士兵坐船时重量增加吃水加深水的阻力增大同样的力量划船速度会变慢3由于河水湍急大量的力用来抵消水流的阻力所以2中过河用时不是a[i] *2而是a[i] * 10。三、示例输入54312 13 15 20 50输出3 40说明可以达到或小于43的一种方案第一步a[0] a[1] 过河用时13第二步a[0] 返回用时12第三步a[0] a[2] 过河用时15输入513050 12 13 15 20输出5 128说明可以达到或小于130的一种方案第一步a[1] a[2] 过河用时13第二步a[1] 返回用时12第三步a[0] a[4] 过河用时50第四步a[2] 返回用时13第五步a[1] a[2] 过河用时13第六步a[1] 返回用时12第七步a[1] a[3] 过河用时15所以输出为5 128输入717125 12 13 15 20 35 20输出7 171说明可以达到或小于171的一种方案第一步a[1] a[2] 过桥用时13第二步a[1] 带火把返回用时12第三步a[0] a[5] 过桥用时35第四步a[2] 带火把返回用时13第五步a[1] a[2] 过桥用时13第六步a[1] 带火把返回用时12第七步a[4] a[6] 过桥用时20第八步a[2] 带火把返回用时13第九步a[1] a[3] 过桥用时15第十步a[1] 带火把返回用时12第十一步a[1] a[2] 过桥用时13所以输出为7 171四、解题思路1. 核心思想结合二分查找快速定位最大可行人数经典多人过河问题的最优耗时公式先通过二分法枚举可能的过河人数再对每个人数计算其最短过河时间最终找到 “耗时≤上限” 的最大人数及对应最短时间。核心是 “二分法缩小可行人数范围经典公式保证耗时最优两者结合高效求解”。2. 问题本质分析表层问题在时间上限内找到最多过河的士兵数并计算其最短耗时深层问题人数与耗时的单调性过河人数越多最短耗时必然≥更少人数的最短耗时单调性因此可通过二分法高效枚举过河耗时的最优解问题经典多人过河问题的核心是 “让耗时短的士兵多往返划船”通过固定公式可快速计算指定人数的最短耗时无需暴力枚举路径最优策略的选择≥4 人时两种策略的耗时对比是减少总耗时的关键避免无效的往返排序的必要性优先选择耗时短的士兵过河才能最大化可行人数耗时短的人参与往返总耗时更低。3. 核心逻辑排序预处理将士兵过河耗时升序排序保证每次尝试的mid人都是耗时最短的最大化可行人数二分查找利用 “人数越多最短耗时越高” 的单调性枚举可能的过河人数mid耗时计算对每个mid调用经典过河问题的最优耗时公式计算mid人的最短过河时间边界调整根据耗时与上限的关系调整二分边界记录满足条件的最大人数及对应耗时。4. 步骤拆解输入预处理读取士兵数、时间上限、过河耗时数组对耗时数组升序排序。二分查找初始化初始化二分边界min0最少人数、maxn最多人数初始化结果字符串ans。二分枚举过河人数循环条件min ≤ max计算中间值mid当前尝试的过河人数截取前mid个耗时最短的士兵调用getMinCrossRiverTime计算其最短耗时need边界调整need limitmid人不可行上界左移maxmid-1need limitmid人可行记录结果下界右移minmid1need limit记录结果并终止循环。最短耗时计算getMinCrossRiverTime剩余人数 1耗时 唯一士兵的耗时剩余人数 2耗时 两人中较长的耗时剩余人数 3耗时 次短 最短 最长剩余人数≥4选两种策略的更优耗时每轮处理 2 人直到剩余人数 4。结果返回输出记录的 “最大人数 最短耗时”。五、代码实现import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int t sc.nextInt(); int[] times new int[n]; for (int i 0; i n; i) { times[i] sc.nextInt(); } System.out.println(getResult(n, t, times)); } /** * param n 士兵数 * param limit 过河时间上限 * param times 数组元素表示每个士兵的过河时长 * return ”最多存活士兵数” “最短用时” */ public static String getResult(int n, int limit, int[] times) { // 过河时间升序 Arrays.sort(times); // 最少成功过河人数 int min 0; // 最多成功过河人数 int max n; // 记录题解 String ans ; // 二分法取可能成功的过河人数 while (min max) { // mid是过河人数 int mid (min max) / 2; // 计算mid个人过河所需的最短时间need int need getMinCrossRiverTime(mid, Arrays.copyOfRange(times, 0, mid)); // 如果need超过了过河时间上限limit那么说明能成功过河的人没这么多 if (need limit) { max mid - 1; } else if (need limit) { // 如果need小于过河时间上限limit那么说明mid个最快的人可以在limit时间内成功过河 ans mid need; // 但是可能还可以过更多人 min mid 1; } else { // 如果need limit那么说明过河人数刚好可以在limit时间内成功过河此时可以直接返回 ans mid need; break; } } return ans; } // 计算将n个人运到河对岸所需要花费的最少时间 public static int getMinCrossRiverTime(int n, int[] t) { int cost 0; while (n 0) { if (n 1) { cost t[0]; break; } else if (n 2) { cost t[1]; break; } else if (n 3) { cost t[1] t[0] t[2]; break; } else { cost Math.min(t[n - 1] t[0] t[n - 2] t[0], t[1] t[0] t[n - 1] t[1]); n - 2; } } return cost; } }