目录
T1：P1049 [NOIP2001 普及组] 装箱问题 - 洛谷
代码：
分析：
T2：P8647 [蓝桥杯 2017 省 AB] 分巧克力 - 洛谷
代码：
分析：
T3：P1824 进击的奶牛 - 洛谷
代码：
分析：
T4：P1036 [NOIP2002 普及组] 选数 - 洛谷
代码：
分析：
T1：P1049 [NOIP2001 普及组] 装箱问题 - 洛谷
代码：
package 蓝桥算法两周训练营__普及组.Day3;
import java.util.Scanner;
/**
* @author yx
* @date 2023-02-07 0:31
*/
public class t1 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int V=scanner.nextInt();
int n=scanner.nextInt();
int[] dp=new int[V+1];
int[] wuPin=new int[n+1];
for (int i = 1; i <= n; i++) {
wuPin[i]=scanner.nextInt();
}
for (int i = 1; i <= n ; i++) {
for (int j = V; j >= wuPin[i] ; j--) {
dp[j]=Math.max(dp[j],dp[j-wuPin[i]]+wuPin[i]);
}
}
System.out.println(V-dp[V]);
}
}
分析：
变种01背包问题，把values[i]改成wuPin[i]，就可以了，题目中问剩余空间最小，其实就是问物品能装的最大空间和01背包的最大价值一模一样
T2：P8647 [蓝桥杯 2017 省 AB] 分巧克力 - 洛谷
代码：
package 蓝桥算法两周训练营__普及组.Day3;
import java.util.Scanner;
/**
* @author yx
* @date 2023-02-07 0:31
*/
public class t2_二分 {
// P8647 [蓝桥杯 2017 省 AB] 分巧克力 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
static int N;
static int K;
static int[] H = new int[N + 1];
static int[] W = new int[N + 1];
public static void main(String[] args) {
/*
二分的难点在于如何确定上界和下界
*/
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
int K = scanner.nextInt();
for (int i = 1; i <= N; i++) {
H[i] = scanner.nextInt();
W[i] = scanner.nextInt();
}
//l不能为0（边长不能为0）
int l = 1;
int r = 100001;
int mid = 0;
//ans是关键
int ans = 0;
//二分查找最优边长
while (l <= r) {
//mid为边长
mid = (l + r) / 2;
if (check(mid)) {
//ans是用来记录count=K时的mid的
ans = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
System.out.println(ans);
}
static boolean check(int mid) {
int count = 0;
for (int i = 1; i <= N; i++) {
count += (H[i] / mid) * (W[i] / mid);
}
if (count >= K) {
return true;
} else {
return false;
}
}
}
分析：
二分最难的是边界问题，只要熟练运用一种即可，这里用的是mid=(r+l)/2，while(l<=r),用一个ans来记录mid，应对check函数中的count=k时的场景
T3：P1824 进击的奶牛 - 洛谷
代码：
package 蓝桥算法两周训练营__普及组.Day3;
import java.util.Arrays;
import java.util.Scanner;
/**
* @author yx
* @date 2023-02-07 0:32
*/
public class t3 {
// T3：P1824 进击的奶牛 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
static int N;
static int C;
static int[] zuoBiao;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
N=scanner.nextInt();
C=scanner.nextInt();
zuoBiao=new int[N+1];
for (int i = 1; i <= N ; i++) {
zuoBiao[i]=scanner.nextInt();
}
Arrays.sort(zuoBiao);
int l=0;
int r=zuoBiao[N]-zuoBiao[1];
int dis=0;
int temp=0;
while (l<=r){
dis=(l+r)/2;
if(check(dis)){//如果true则表示间距过小，可以适当加大
l=dis+1;
temp=dis;
}else {
r=dis-1;
}
}
System.out.println(temp);
}
static boolean check(int dis){
//（1，0）这个坐标肯定是要放牛的
int t=1;
//count=1表示初始位置1是一定要放奶牛的
int count=1;
for (int i = 2; i <= N; i++) {
if(zuoBiao[i]-zuoBiao[t]>=dis){
count++;
t=i;
}
}
if(count>=C){
return true;
}else {
return false;
}
}
}
分析：
此二分延用T2的二分模板，改一下check函数里的函数体即可
T4：P1036 [NOIP2002 普及组] 选数 - 洛谷
代码：
package 蓝桥算法两周训练营__普及组.Day3;
import java.util.Scanner;
/**
* @author yx
* @date 2023-02-07 0:32
*/
public class t4_DFS {
// P1036 [NOIP2002 普及组] 选数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
static int count;
static int[] nums;
static int n,k;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n=scanner.nextInt();
k=scanner.nextInt();
nums=new int[n+1];
count=0;
for (int i = 1; i <= n ; i++) {
nums[i]=scanner.nextInt();
}
//从第一个数字开始
dfs(1,0,0);
System.out.println(count);
}
static void dfs(int step,int geShu,int sum){
//剪枝：个数大于k时，结束递归
if(geShu>k){
return;
}
//剪枝：当遍历完最后一个数时（step=n+1表示（1~n）个数字全部都被遍历过了），结束递归
if(step==n+1) {
if (geShu == k) {
if (isPrime(sum)) {
count++;
}
return;
}
return;
}
/*
无论取不取第Step个数字，都会继续往下递归
*/
//取第Step个数字
dfs(step+1,geShu+1,sum+nums[step]);
//不取第Step个数字
dfs(step+1,geShu,sum);
}
static boolean isPrime(int sum){
for (int j = 2; j*j <= sum ; j++) {
if(sum%j==0){
return false;
}
}
return true;
}
}
分析：
遇到排列问题，就要很快想到dfs，dfs的关键在于剪枝，最后加一个判断素数的函数即可