08/10 12:48

# 一、翻倍

.

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

1
2
``````
``````输入例子2:
2
1 15 4 2
12 19 3 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);

}
}
``````

# 二、跳柱子

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

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

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");
}

}
}

``````

# 三、人数统计

``````输入例子1:
7 4
6 2 1 2 6 2 5
6
5
8
2

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();
}
}

``````

# 四、积木

1、从背包里掏出一块积木（如果有的话）放到当前这一堆里
2、从当前这一堆积木里掏出一块塞到背包里(如果当前积木堆不为空的话)
3、从当前这一堆走到下一堆。

``````输入例子1:
1
5 3
2 2 3 3 1

YES
``````
``````输入例子2:
1
5 2
0 0 1 2 1

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();
}
}

``````

0
0 收藏

0 评论
0 收藏
0