2-18算法习题总结

二分查找问题

[COCI 2011/2012 #5] EKO / 砍树

题目描述

伐木工人 Mirko 需要砍 $M$ 米长的木材。对 Mirko 来说这是很简单的工作，因为他有一个漂亮的新伐木机，可以如野火一般砍伐森林。不过，Mirko 只被允许砍伐一排树。

Mirko 的伐木机工作流程如下：Mirko 设置一个高度参数 $H$（米），伐木机升起一个巨大的锯片到高度 $H$，并锯掉所有树比 $H$ 高的部分（当然，树木不高于 $H$ 米的部分保持不变）。Mirko 就得到树木被锯下的部分。例如，如果一排树的高度分别为 $20,15,10$ 和 $17$，Mirko 把锯片升到 $15$ 米的高度，切割后树木剩下的高度将是 $15,15,10$ 和 $15$，而 Mirko 将从第 $1$ 棵树得到 $5$ 米，从第 $4$ 棵树得到 $2$ 米，共得到 $7$ 米木材。

Mirko 非常关注生态保护，所以他不会砍掉过多的木材。这也是他尽可能高地设定伐木机锯片的原因。请帮助 Mirko 找到伐木机锯片的最大的整数高度 $H$，使得他能得到的木材至少为 $M$ 米。换句话说，如果再升高 $1$ 米，他将得不到 $M$ 米木材。

输入格式

第 $1$ 行 $2$ 个整数 $N$ 和 $M$，$N$ 表示树木的数量，$M$ 表示需要的木材总长度。

第 $2$ 行 $N$ 个整数表示每棵树的高度。

输出格式

$1$ 个整数，表示锯片的最高高度。

样例 #1

样例输入 #1

4 7
20 15 10 17

样例输出 #1

15

样例 #2

样例输入 #2

5 20
4 42 40 26 46

样例输出 #2

36

提示

对于 $100\%$ 的测试数据，$1\le N\le 10^6$，$1\le M\le 2\times 10^9$，树的高度 $\le 4\times 10^5$，所有树的高度总和 $>M$。

这道题我还没写出来

动态规划问题

疯狂的采药

题目背景

此题为纪念 LiYuxiang 而生。

题目描述

LiYuxiang 是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同种类的草药，采每一种都需要一些时间，每一种也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”

如果你是 LiYuxiang，你能完成这个任务吗？

此题和原题的不同点：

$1$. 每种草药可以无限制地疯狂采摘。

$2$. 药的种类眼花缭乱，采药时间好长好长啊！师傅等得菊花都谢了！

输入格式

输入第一行有两个整数，分别代表总共能够用来采药的时间 $t$ 和代表山洞里的草药的数目 $m$。

第 $2$ 到第 $(m+1)$ 行，每行两个整数，第 $(i+1)$ 行的整数 $a_i,b_i$ 分别表示采摘第 $i$ 种草药的时间和该草药的价值。

输出格式

输出一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。

样例 #1

样例输入 #1

70 3
71 100
69 1
1 2

样例输出 #1

140

提示

数据规模与约定

• 对于 $30\%$ 的数据，保证 $m\le 10^3$ 。
• 对于 $100\%$ 的数据，保证 $1\le m\le 10^4$，$1\le t\le 10^7$，且 $1\le m\times t\le 10^7$，$1\le a_i,b_i\le 10^4$。

最后一个测试点没过

代码如下:

package exercise.luogu.dp;import java.util.Scanner;public class P1616 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int t = sc.nextInt();int n = sc.nextInt();int[] val = new int[n];int[] time = new int[n];int dp[] = new int[t + 1];for (int i = 0; i < n; i++) {time[i] = sc.nextInt();val[i] = sc.nextInt();}// 完全背包问题：每种药材都可以采多次for (int i = 0; i < n; i++) { // 遍历每种药材for (int j = time[i]; j <= t; j++) { // 遍历背包容量，注意从time[i]开始// 当前药材可以放入背包中，比较放入与不放入哪种情况价值更高dp[j] = Math.max(dp[j], dp[j - time[i]] + val[i]);}}System.out.println(dp[t]);}
}

总结:
我感觉完全背包问题比部分背包问题要简单得多!

贪心问题

删数问题

题目描述

键盘输入一个高精度的正整数 $N$（不超过 $250$ 位），去掉其中任意 $k$ 个数字后剩下的数字按原左右次序将组成一个新的非负整数。编程对给定的 $N$ 和 $k$，寻找一种方案使得剩下的数字组成的新数最小。

输入格式

输入两行正整数。

第一行输入一个高精度的正整数 $n$。

第二行输入一个正整数 $k$，表示需要删除的数字个数。

输出格式

输出一个整数，最后剩下的最小数。

样例 #1

样例输入 #1

175438 
4

样例输出 #1

13

代码如下:

package exercise.luogu.greedy;import java.util.Scanner;
import java.util.Stack;public class P1106 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);String str = sc.next();int k = sc.nextInt();char[] charArray = str.toCharArray();Stack<Character> stack = new Stack<>();int removeCount = 0;for (int i = 0; i < charArray.length; i++) {//如果栈顶元素大于当前元素,pop出栈顶元素,把当前元素加入栈while (!stack.isEmpty() && stack.peek() > charArray[i] && removeCount < k) {stack.pop();removeCount++;}stack.push(charArray[i]);}// 如果还有需要删除的数字，则从栈顶开始删除while (removeCount < k) {stack.pop();removeCount++;}// 将栈中的数字转换为字符串并输出StringBuilder sb = new StringBuilder();while (!stack.isEmpty()) {sb.append(stack.pop());}sb.reverse(); // 因为栈是后进先出的，所以需要反转字符串才能得到正确的结果System.out.println(Integer.parseInt(sb.toString()));}
}

分支问题

【模板】快速幂

题目描述

给你三个整数 $a,b,p$，求 $a^b\mathrm{mod}p$。

输入格式

输入只有一行三个整数，分别代表 $a,b,p$。

输出格式

输出一行一个字符串 a^b mod p=s，其中 $a,b,p$ 分别为题目给定的值， $s$ 为运算结果。

样例 #1

样例输入 #1

2 10 9

样例输出 #1

2^10 mod 9=7

提示

样例解释

$2^{10}=1024$，$1024\mathrm{mod}9=7$。

数据规模与约定

对于 $100\%$ 的数据，保证 $0\le a,b<2^{31}$，$a+b>0$，$2\le p<2^{31}$。

代码如下:

package exercise.luogu.fenzhi;import java.util.Scanner;public class P1226 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int a = sc.nextInt();int b = sc.nextInt();int p = sc.nextInt();int s = fastPowMod(a, b, p);System.out.printf("%d^%d mod %d=%d", a, b, p, s);}//快速幂算法private static int fastPowMod(int a, int b, int p) {if (b == 0) {return 1;}int halfMod = fastPowMod(a, b / 2, p);int modSquare = (int) (((long) halfMod * halfMod) % p);//如果 b 是偶数，那么 a^b = (a^(b/2))^2。if (b % 2 == 0) {return modSquare;} else {//如果 b 是奇数，那么 a^b = a * (a^(b-1))。//我们首先计算 a^((b-1)/2) mod p（这仍然是 halfMod，因为整数除法会向下取整）return (int) (((long) modSquare * a) % p);}}
}