如果你从本文中学习到丝毫知识，那么请您点点关注、、评论和
大家好，我是爱做梦的鱼，我是东北大学大数据实验班大三的小菜鸡，非常渴望优秀，羡慕优秀的人，个人博客为：爱做梦的鱼https://zihao.blog.csdn.net/，微信公众号、微信视频号为【程序猿干货铺】，qq交流群为：1107710098，

本题出处——牛客链接：https://www.nowcoder.com/test/20791044/summary

一、翻倍

时间限制： C/C++ 2秒，其他语言4秒
空间限制： C/C++ 256M，其他语言512M

小易给定你数字
$A，B (A<B)$

A，B(A<B) 和系数
$p，q$

p，q。每次操作你可以将 A 变成
$A+p$

A+p 或者 p 将变成
$ptimes q$

p×q 。问至少几次操作使得
$B leq A$

B≤A 。

输入描述:
第一行数据组数
$T$

T，对于每组数据，一行四个整数
$A，B，p，q$

A，B，p，q。

$1leq A,p,B leq10^9$

1≤A,p,B≤109,
$2leq q leq10$

2≤q≤10,
$1leq T leq5$

1≤T≤5
.
输出描述:
对于每组数据，输出一个数字表示答案

输入例子1: 2 1 5 7 2 3 5 1 2  输出例子1: 1 2 

输入例子2: 2 1 15 4 2 12 19 3 2  输出例子2: 3 3 

方法一：暴力

import java.util.Scanner; /**  * Created by IntelliJ IDEA.  *  * @Author: 张志浩 Zhang Zhihao  * @Email: 3382885270@qq.com  * @Date: 2020/8/7  * @Time: 15:00  * @Version: 1.0  * @Description: Description  */ public class Doubled { public static void main(String[] args) {         Scanner sc = new Scanner(System.in); int T = sc.nextInt(); for (int i = 0; i < T; i++) {             System.out.println(count(sc.nextInt(), sc.nextInt(), sc.nextInt(), sc.nextInt())); }         sc.close(); } public static int count(int A, int B, long p, int q) { int res = 1; while (A < B) { if (A + p >= B) { return res; } else {                 p = p * q;                 res++; } } /*while (A + p < B) {             p = p * q;             res++;         }*/ return res; } } 

方法二：递归

import java.util.Scanner; /**  * Created by IntelliJ IDEA.  *  * @Author: 张志浩 Zhang Zhihao  * @Email: 3382885270@qq.com  * @Date: 2020/8/7  * @Time: 16:51  * @Version: 1.0  * @Description: Description  */ public class Doubled2 { public static void main(String[] args) {         Scanner in = new Scanner(System.in); int t = in.nextInt(); for (long i = 0; i < t; i++) { long a = in.nextLong(); long b = in.nextLong(); long p = in.nextLong(); long q = in.nextLong(); long nums = getDoubling(a, b, p, q, 0);             System.out.println(nums); } } private static long getDoubling(long a, long b, long p, long q, long nums) { if (a + p >= b) return nums + 1; else if (a + p * q >= b) return nums + 2; else return getDoubling(a, b, p * q * q, q, nums + 2); } } 

二、跳柱子

时间限制： C/C++ 2秒，其他语言4秒

空间限制： C/C++ 256M，其他语言512M

小易有
$n$

n 根柱子，第i根柱子的高度为
$h_i$

hi​ 。一开始小易站在第一根柱子上。小易能从第
$i$

i 根柱子跳到第
$j$

j 根柱子，当且仅当且
$h_j leq h_i$

hj​≤hi​ 且
$1leq j-i leq k$

1≤j−i≤k 。其中为指定的一个数字。
另外小易拥有一次释放超能力的机会。这个超能力能让小易从柱子 i 跳到任意满足
$1leq j-i leq k$

1≤j−i≤k 的柱子 j 而无视柱子高度的限制。
现在小易想知道，小易是否能到达第 n 根柱子。

输入描述:
第一行数据组数
$T$

T
对于每组数据，第一行数字
$n , k$

n,k ，接下来一行
$n$

n 个数字表示
$h_i$

hi​.

$1leq n leq 1000$

1≤n≤1000 ,
$1leq h_i leq 10^9$

1≤hi​≤109 ,
$1leq T leq 10$

1≤T≤10 ,
$1leq k leq n$

1≤k≤n

输出描述:
对于每组数据，输出YES或NO

输入例子1: 1 5 3 6 2 4 3 8  输出例子1: YES 

输入例子2: 1 5 2 1 8 2 3 4  输出例子2: NO 

方法一：暴力，寻找能到达的最高柱子，方便我下次跳

/**  * Created by IntelliJ IDEA.  *  * @Author: 张志浩 Zhang Zhihao  * @Email: 3382885270@qq.com  * @Date: 2020/8/8  * @Time: 10:28  * @Version: 1.0  * @Description: Description  */ import java.util.Scanner; public class JumpPillar5_Violence { public static void main(String[] args) {         Scanner sc = new Scanner(System.in); int T = sc.nextInt(); int n = 0, k = 0; for (int i = 0; i < T; i++) {             n = sc.nextInt();             k = sc.nextInt(); int[] nums = new int[n]; for (int j = 0; j < n; j++)                 nums[j] = sc.nextInt();             System.out.println(solution(n, k, nums)); } } public static String solution(int n, int k, int[] nums) { int big = 1; int index = 0; while (index < nums.length - 1) { int tmp = index; int max = 0, max_index = index; for (int j = index + 1; j < index + 1 + k && j < nums.length; j++) { if (nums[j] < nums[index]) {                     max_index = (max > nums[j]) ? max_index : j;                     max = Math.max(nums[j], max); } }             index = max_index; if (tmp == index && big > 0) {                 big--;                 max = 0;                 max_index = index; for (int j = index + 1; j < index + 1 + k && j < nums.length; j++) {                     max_index = (max > nums[j]) ? max_index : j;                     max = Math.max(nums[j], max); }                 index = max_index; } else if (tmp == index && big <= 0) return "NO"; } return "YES"; } } 

方法二：动态规划dp

/**  * Created by IntelliJ IDEA.  *  * @Author: 张志浩 Zhang Zhihao  * @Email: 3382885270@qq.com  * @Date: 2020/8/8  * @Time: 9:54  * @Version: 1.0  * @Description: Description  */ import java.util.Scanner; public class JumpPillar3 { public static void main(String[] args) {          Scanner sc = new Scanner(System.in); int m = sc.nextInt(); while (m-- > 0) { int n = sc.nextInt(); int k = sc.nextInt(); int[] a = new int[n]; for (int i = 0; i < n; i++) {                 a[i] = sc.nextInt(); } int[] dp = new int[n];             dp[0] = 1; for (int i = 0; i < n; i++) { if (dp[i] > 0) { for (int j = i + 1; j <= i + k && j < n; j++) { if (a[i] >= a[j]) { if (dp[j] == 0 || dp[j] > dp[i])                                 dp[j] = dp[i]; } else if (dp[i] == 1 && dp[j] == 0)                             dp[j] = 2; } } }              System.out.println(dp[n - 1] > 0 ? "YES" : "NO"); } } } 

三、人数统计

时间限制： C/C++ 2秒，其他语言4秒

空间限制： C/C++ 256M，其他语言512M

小易的公司一共有 n 名员工, 第个人每个月的薪酬是
$x_i$

xi​ 万元。
现在小易的老板向小易提了次询问, 每次询问老板都会给出一个整数 k 小易要快速回答老板工资等于 k 的员工的数量。

输入描述:
第一行，两个空格间隔的整数 n 和 m ,表示人数和提问的次数
第二行，n 个用空格间隔的整数
$x_i$

xi​ ，表示每名员工的薪酬
接下来有 m 行，每行一个整数，表示老板的一次提问。

$1leq m leq 80000$

1≤m≤80000 ,
$1leq n leq 100000$

1≤n≤100000 ,
$1leq x_i leq 500,000,000$

1≤xi​≤500,000,000

输出描述:
m 行，每行一个整数，表示对应提问的答案

输入例子1: 7 4 6 2 1 2 6 2 5 6 5 8 2  输出例子1: 2 1 0 3 

方法：哈希表

import java.util.HashMap; import java.util.Map; import java.util.Scanner; /**  * Created by IntelliJ IDEA.  *  * @Author: 张志浩 Zhang Zhihao  * @Email: 3382885270@qq.com  * @Date: 2020/8/7  * @Time: 22:19  * @Version: 1.0  * @Description: Description  */ public class PeopleCount { public static void main(String[] args) {         Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt();         Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < n; i++) { int x = sc.nextInt();             map.put(x, map.getOrDefault(x, 0) + 1); } for (int i = 0; i < m; i++) { int k = sc.nextInt(); if (map.get(k) == null) {                 System.out.println(0); } else {                 System.out.println(map.get(k)); } }         sc.close(); } } 

四、积木

时间限制： C/C++ 2秒，其他语言4秒

空间限制： C/C++ 256M，其他语言512M

小易有 n 堆积木，第 i 堆积木有
$h_i$

hi​ 块。小易还拥有一个容量无限的背包。
一开始小易站在第一堆积木旁边。每次小易可以选择进行下列三种操作中的一种：
1、从背包里掏出一块积木（如果有的话）放到当前这一堆里
2、从当前这一堆积木里掏出一块塞到背包里(如果当前积木堆不为空的话)
3、从当前这一堆走到下一堆。
一开始小易的背包里有 m 块积木。小易希望把这些个积木变成严格递增的（即
$h_1 < h_2 < h_3 ··· <h_n$

h1​<h2​<h3​⋅⋅⋅<hn​ 。小易希望知道这是否有可能能完成。（所有操作结束后不需要保证背包里没有积木了，可以有积木堆为空）。

输入描述:
第一行数据组数 T
对于每组数据，第一行数字 n , m，接下来一行 n 个数字表示
$h_i$

hi​ .

$1leq n leq 100000$

1≤n≤100000 ,
$0leq h_i leq 10^9$

0≤hi​≤109 ,
$1leq T leq 10$

1≤T≤10 ,
$1=0leq m leq 10^9$

1=0≤m≤109

输出描述:
对于每组数据输出一行，输出结果 YES 或 NO

输入例子1: 1 5 3 2 2 3 3 1  输出例子1: YES 

输入例子2: 1 5 2 0 0 1 2 1  输出例子2: NO 

方法

package nowcoder; import java.util.Scanner; /**  * Created by IntelliJ IDEA.  *  * @Author: 张志浩 Zhang Zhihao  * @Email: 3382885270@qq.com  * @Date: 2020/8/8  * @Time: 11:26  * @Version: 1.0  * @Description: Description  */ public class BuildingBlock { public static void main(String[] args) {         Scanner sc = new Scanner(System.in); int T = sc.nextInt(); for (int i = 0; i < T; i++) { int n = sc.nextInt(); long sum = sc.nextInt(); //m boolean flag = true; int[] arr = new int[n]; for (int j = 0; j < n; j++) {                 arr[j] = sc.nextInt(); } for (int j = 0; j < n; j++) {                 sum += arr[j]; if (sum < j * (j + 1) / 2) {                     System.out.println("NO");                     flag = false; break; } } if (flag) {                 System.out.println("YES"); } }         sc.close(); } }