题目一：有n座山每一座山的高度是H[i] 假设当前在i位置，接下来可以进行下面两个操作之一 1.走到相邻的山，代价是 min（0，H[j] - H[i]） 2.发动闪现到任意位置 代价是p 2 <= n <=2e5 0<= p <= 1e9 0 <= H[i] <= 1e9 输入n和p，然后输入H[i] 输出走完所有山的最小代价
1.输入
6` `5` `100` `1` `3` `0` `10` `100
输出
7
2.输入
6 3 1 1 10 10 100 100
输出
3
3.输入
6 5 0 6 6 0 6 6
输出
10
4.输入
6 5 0 6 0 6 0 6
输出
15
5.输入
10 5 100 1 2 3 0 5 19 100 0 100
输出
12
- 思路讲解在解题代码中体现
代码解法：
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
//n个凉亭
int n = scanner.nextInt();
//移动任意距离消耗p个能量
int p = scanner.nextInt();
int target =0;
//记录亭子数量
int[] tingZiNums = new int[n+1];
Arrays.fill(tingZiNums,1000000001);
for (int i = 0; i < n ; i++) {
tingZiNums[i] = scanner.nextInt();
}
//记录初始临时量,阶段最低点
int tmp = 0;
if(tingZiNums[0]>=tingZiNums[1]){
tmp = tingZiNums[1];
}else {
tmp = tingZiNums[0];
}
//记录阶段最低点tmp的元素下标
int preNum = 0;
//从第二个位置起，开始遍历所有元素
for (int i = 1; i < n; i++) {
//遇到阶段性的高点，进行逻辑处理，否则继续往下遍历
if(tingZiNums[i]>=tmp&&tingZiNums[i+1]>=tingZiNums[i]){
//当元素为最后一个时，且最后一个元素为阶段性最高点，进行逻辑处理
if(i==tingZiNums.length-2){
if(tingZiNums[i]-tmp>=p){
target += p;
tmp = tingZiNums[i+1];
preNum = i+1;
}else {
target += tingZiNums[i]-tmp;
tmp = tingZiNums[i+1];
preNum = i+1;
}
}
continue;
}else {
//遇到下一个元素比当前元素小，进行逻辑处理
if(tingZiNums[i]-tmp>=p){
int k =0;
k=i;//解决平顶平底问题
//直接移至最高层，然后再返回其他低的层级
target += p;
tmp = tingZiNums[i+1];
preNum = i+1;
int j = 0;
//解决从下降的最低位置重新返回到下个临时起始位置
for (j = preNum; j < n+1 ; j++) {
if(tmp == tingZiNums[j]){
break;
}
}
for (int l = 0; l < n+1 ; l++) {
if(tingZiNums[k]==tingZiNums[k-1]){
k--;
}else {
break;
}
}
//如果不是相邻的层级，需要直接跳跃至下一个最低点层级，消耗p能量
if(k-j>=2){
target +=p;
}
}else {
//逐层往上走
target += tingZiNums[i]-tmp;
tmp = tingZiNums[i+1];
preNum = i+1;
}
}
}
System.out.println(target);
}
}
题目二、题目描述 牛牛最近工作繁忙，纷至沓来的任务让牛牛感到焦头烂额。他想以一种高效的方式来工作，因此他根据数据结构中所学的知识找到了一种解决方法—把完成每项任务所需的时间存储下来，并按一定的顺序执行。 牛牛所想到的数据结构是队列。队列是计算机的基本数据结构之一，它是一种采用FIFO （先进先出）的结构存储数据的方法。 牛牛也注意到了这种方法存在的弊端：所有的任务都要按顺序执行，但是牛牛的工作时间是固定的，一旦出现需要处理的紧急事务，很可能无法及时解决。所以，牛牛首先需要预测一下，自己在不同的工作时间内分别能够处理多少常规任务。 输入描述： 第一行输入整数N和M，分别代表工作任务的总数和待测的工作时间的数量，其间以空格隔开。 第二行输入N个整数t，分别表示每项任务所需的工作时间，t；表示第一项任务...依此类推，其间以空格隔开。 接下来的M行，每行输入对应的不同工作时间T。1 1.输入： 输出： 2.输入： 输出： 3.输入： 输出： 代码解法： 题目三：思路讲解：直接遍历题目给定的N*N二维数组，定义一个long类型的res变量，将二维数组的值直接全部累加即可，输出最后的结果res的值。 时间复杂度：O（n的平方）7 4 1 2 3 1 2 3 1
1 8 11 14
1
4
5
7
5 4 1 2 3 4 5 1 2 3 4
1
1
2
2
8 4 1 10 4 5 5 4 10 1
11
20
29
40
2
4
6
8
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[] taskNumsTime = new int[n];
int[] haveTime = new int[m];
for (int i = 0; i < n ; i++) {
taskNumsTime[i] = scanner.nextInt();
}
for (int i = 0; i < m; i++) {
haveTime[i] = scanner.nextInt();
}
int[] target = new int[m];
int tmp =0;
int finishtask =0;
//优化时间复杂度；preTaskData[0]: 代表j; 记录 任务时间起始位置下标
// preTaskData[1] :tmp; 记录j 之前的时间和
//preTaskData[2] :finishtask 记录j 之前的时间能完成的任务数
int[] preTaskData = new int[3];
Arrays.fill(preTaskData,0);
for (int i = 0; i < m; i++) {
for (int j = preTaskData[0]; j < n; j++,preTaskData[0]++) {
tmp += taskNumsTime[j];
if(tmp<=haveTime[i]){
finishtask++;
target[i] = finishtask;
preTaskData[1] = tmp;
preTaskData[2] =finishtask;
}else {
tmp = preTaskData[1];
finishtask = preTaskData[2];
target[i] = finishtask;
break;
}
}
}
for (int i = 0; i < m; i++) {
System.out.println(target[i]);
}
}
}
