【c++笔试强训】（第三十二篇）
目录
数组变换（贪⼼+位运算）
题目解析
讲解算法原理
编写代码
装箱问题（动态规划-01背包）
题目解析
讲解算法原理
编写代码
数组变换（贪⼼+位运算）
题目解析
1.题目链接：数组变换__牛客网
2.题目描述
牛牛有一个数组，里面的数可能不相等，现在他想把数组变为：所有的数都相等。问是否可行。
牛牛可以进行的操作是：将数组中的任意一个数改为这个数的两倍。这个操作的使用次数不限，也可以不使用，并且可以对同一个位置使用多次。
数据范围：数组大小满足 1≤n≤50 1 \le n \le 50 \ 1≤n≤50 ，数组中的数满足 1≤val≤109 1 \le val \le 10^{9} \ 1≤val≤109
输入描述:
输入一个正整数N (N <= 50)
接下来一行输入N个正整数，每个数均小于等于1e9.输出描述:
假如经过若干次操作可以使得N个数都相等，那么输出"YES", 否则输出"NO"
示例1
输入
2
1 2输出
YES
示例2
输入
3
1 2 3输出
NO
讲解算法原理
解法：
算法思路：
如果能够变换成功，那么最⼤的数除以剩下的数的商，⼀定都是2的n次⽅。
编写代码
c++算法代码：
#include <iostream>
using namespace std;
int b;
int n;
int arr[51];
bool fun()
{for(int i = 0; i < n; i++){if(b % arr[i]) return false; int x = b / arr[i]; if(x - (x & -x)) return false; } return true;
}
int main()
{cin >> n;for(int i = 0; i < n; i++){cin >> arr[i]; b = max(b, arr[i]); }if(fun()) cout << "YES" << endl; else cout << "NO" << endl;return 0;
}Java算法代码：
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main
{public static void main(String[] args) {Scanner in = new Scanner(System.in); int n = in.nextInt(); int[] arr = new int[n]; int b = 0;for(int i = 0; i < n; i++){arr[i] = in.nextInt(); b = Math.max(b, arr[i]); }boolean flag = true; for(int i = 0; i < n; i++) { if(b % arr[i] != 0) { flag = false; break;}int x = b / arr[i]; if((x - (x & -x)) != 0) { flag = false; break;}}if(flag) System.out.println("YES"); else System.out.println("NO"); }
}装箱问题（动态规划-01背包）
题目解析
1.题目链接：登录—专业IT笔试面试备考平台_牛客网
2.题目描述
题目描述
有一个箱子容量为V（正整数，0 ≤ V ≤ 20000），同时有n个物品（0＜n ≤ 30），每个物品有一个体积（正整数）。
要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。输入描述:
1个整数，表示箱子容量
1个整数，表示有n个物品
接下来n行，分别表示这n个物品的各自体积输出描述:
1个整数，表示箱子剩余空间。
示例1
输入
24 6 8 3 12 7 9 7
24
6
8
3
12
7
9
7输出
0
0
讲解算法原理
解法：
算法思路：
01背包简单应⽤。
编写代码
c++算法代码：
#include <iostream>
using namespace std;
const int N = 35, M = 2e4 + 10;
int n, v;
int arr[N];
int dp[N][M];
int main()
{cin >> v >> n;for(int i = 1; i <= n; i++){cin >> arr[i];}for(int i = 1; i <= n; i++){for(int j = 0; j <= v; j++){dp[i][j] = dp[i - 1][j]; if(j >= arr[i]){dp[i][j] = max(dp[i][j], dp[i - 1][j - arr[i]] + arr[i]);}}}cout << (v - dp[n][v]) << endl;return 0;
}Java算法代码：
import java.util.*;
public class Main
{public static void main(String[] args){Scanner in = new Scanner(System.in); int v = in.nextInt(); int n = in.nextInt(); int[] arr = new int[n + 1];for(int i = 1; i <= n; i++){arr[i] = in.nextInt();}int[][] dp = new int[n + 1][v + 1]; for(int i = 1; i <= n; i++) { for(int j = 0; j <= v; j++) { dp[i][j] = dp[i - 1][j]; if(j >= arr[i]){dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - arr[i]] + arr[i]); }}}System.out.println(v - dp[n][v]);}
}