算法每日一题3

2023-04-11

竞赛 / 算法 / 每日一题

Word count: 2.5k | Reading time≈ 11 min

每日一题

每日一题系列旨在督促本人坚持算法练习，并期望将之养成一个习惯。

1、跳石头

lanqiao-364：跳石头 - 蓝桥云课 (lanqiao.cn)

完成时间：2023年4月1日23:43:05

tags：二分法

$\textcolor{red}{分析：}$

注意题目中的至多移走m块石头，那么当移走的石头越多，那么最短跳跃距离就越大，反之则越小；
所以我们必须保证小于m而尽可能大于接近于m，实质是在所有可能的最小值中，找最大的那个，就是“最小值最大化”
所以应该求得是：在单调递增序列d中查找<=x的数中最大的一个（即x或x的前趋）；
这里转换成了由当前d得到的可以移动的石头数量num与至多可以移动的数量m之间的比较。

解决代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5;
int len, n, m;// 分别为起点到终点的距离，起点和终点之间的岩石数，以及组委会至多移走的岩石数 
int stone[N];

bool check(int d){// 验证最短跳跃距离d是否满足条件 
	int pos = 0;// 当前位置 
	int num = 0;// 移去石头的数量 
	for(int i=1;i<=n;++i){
		if(stone[i] - pos < d){
			num++;// 符合要求可以去掉石头 
		}else{
			pos = stone[i];// 更新当前位置，表示的是在前一个[pos,pos+d]内已经去除了最多的石头数 
		} 
	} 
	if(num<=m)return true;// 满足至多移去m个石头 
	else return false; 
}

int main() {
	cin>>len>>n>>m;
	for(int i=1;i<=n;++i){
		cin>>stone[i];// 初始化石头到起点的距离 
	}
	// 在单调递增序列a中查找<=x的数中最大的一个（即x或x的前趋）
	int L = 0, R = len;
	while(L<R){
		int mid = (L + R + 1)/2;
		if(check(mid)){// 如果成立，那么表明当前的mid小了点，应该增大 
			L = mid;
		}else{		// 否则表明当前的mid大了点，应该减小  
			R = mid - 1;
		}
	}
	cout<<L;
	return 0;
}

2、完全背包问题

AcW-3：3. 完全背包问题 - AcWing题库

完成时间：2023年4月2日

tags：动态规划、背包问题

$\textcolor{red}{分析：}$

每种物品都有无限件可用；
普通做法（采用二维数组）；
空间压缩（采用一维数组、对容量顺序遍历）；

解决代码：

#include<bits/stdc++.h>
using namespace std;
// 完全背包问题 
const int N = 1e3+10;
int dp[N][N], v[N], w[N];// v体积，w价值 
int n, V, res;
int f[N];

int main() {
	cin>>n>>V;
	for(int i=1;i<=n;++i){
		cin>>v[i]>>w[i];
	}
	res = 0;
	dp[0][0] = 0;
//	for(int i=1;i<=n;++i){
//		for(int j=0;j<=V;++j){
//			dp[i][j] = dp[i-1][j];
//			if(j>=v[i]){
//				dp[i][j] = max(dp[i][j], dp[i][j-v[i]]+w[i]);
//			}
//			res = max(res, dp[i][j]);
//		}
//	}
	//空间压缩
	for(int i=1;i<=n;++i){
		for(int j=0;j<=V;++j){// 完全背包问题顺序遍历 
			if(j>=v[i]){
				f[j] = max(f[j], f[j-v[i]]+w[i]);
			}
		}
	}
//	cout<<res;
	cout<<f[V];
	return 0;
}

3、多重背包问题 I

AcW-4：4. 多重背包问题 I - AcWing题库

完成时间：2023年4月2日

tags：动态规划、背包问题

$\textcolor{red}{分析：}$

转换为01背包问题解决；
在01背包的基础上添加数量条件限制（注意：状态转移方程有些许不同——dp[i][j] = max(dp[i][j], dp[i-1][j-k*v[i]]+k*w[i]),k必须从0开始）；

解决代码：

#include<bits/stdc++.h>
using namespace std;
// 多重背包问题 ——添加附加数量限制条件 
const int N = 1e3+10;
int dp[N][N], v[N], w[N], s[N];// v体积，w价值，s数量 
int n, V;
int f[N];

int main() {
	cin>>n>>V;
	for(int i=1;i<=n;++i){
		cin>>v[i]>>w[i]>>s[i];
	}
	for(int i=1;i<=n;++i){
		for(int j=0;j<=V;++j){
			for(int k=0;k<=s[i];++k){// 这里的k必须从0开始,k=0时有dp[i-1][j] 
				if(j>=k*v[i]){
					dp[i][j] = max(dp[i][j], dp[i-1][j-k*v[i]]+k*w[i]);// 在01-背包问题的基础上作次数限制 
				}
			}
		}
	}
	//空间压缩
//	for(int i=1;i<=n;++i){
//		for(int j=V;j>=v[i];--j){
//			for(int k=1;k*v[i]<=j&&k<=s[i];++k){
//				f[j] = max(f[j], f[j-k*v[i]]+k*w[i]);
//			}
//		}
//	}
	cout<<dp[n][V];
//	cout<<f[V];
	return 0;
}

4、快乐司机

lanqiao-1513：第十四届蓝桥杯省赛冲刺营【第二期】 - 【课后练习】快乐司机 - 蓝桥云课 (lanqiao.cn)

完成时间：2023年4月3日

tags：贪心算法

【题目描述】话说现在当司机光有红心不行，还要多拉快跑。多拉不是超载，是要让所载货物价值最大，特别是在当前油价日新月异的时候。司机所拉货物为散货，如大米、面粉、沙石、泥土⋯现在知道了汽车核载重量为w，可供选择的物品的数量n。每个物品的重量为gi, 价值为pi。求汽车可装载的最大价值。（n<10000,w<10000,0<gi≤100,0≤pi≤100)。

【输入描述】输入第一行为由空格分开的两个整数n,w。第二行到第n+1行，每行有两个整数，由空格分开，分别表示gi和pi。

【输出描述】最大价值（保留一位小数）。

$\textcolor{red}{分析：}$

因为所拉货物为散货，因此可以装一部分，由此我们需要计算每种货物的单位价值（pi/gi）；

解决代码：

#include<bits/stdc++.h>
using namespace std;

const int N = 1e4+10;
struct node{
	double v, w, scale;// 分别为价值、重量、单位价值 
}; 
node product[N];
int n;
double W;
double res = 0;

bool comp(node&a, node&b){// 降序排序 
	return a.scale>b.scale;
}

int main() {
	cin>>n>>W;
	for(int i=1;i<=n;++i){
		cin>>product[i].w>>product[i].v;
		product[i].scale = product[i].v/product[i].w;
	}
	sort(product+1, product+1+n, comp);// 针对scale排序 
	for(int i=1;i<=n;++i){
		if(W>=product[i].w){
			res += product[i].v;// 价值增加 
			W -= product[i].w;// 重量减少 
		}else{
			res += W*product[i].scale;// 剩余重量与单位价值之积 
			break;// 结束 
		}
	}
	printf("%.1f", res);
	return 0;
}

5、防御力

lanqiao-226：防御力 - 蓝桥云课 (lanqiao.cn)

完成时间：2023年4月3日

tags：贪心算法

$\textcolor{red}{分析：}$

要求字典序最小的使用道具的方式；
根据分析知道A从小到大排序，B从大到小排序；
PS：这道题编码简单，但是为什么是这样做的值得认真思考和证明！

解决代码：

#include<bits/stdc++.h>
using namespace std;
// 根据分析知道A从小到大排序，B从大到小排序

int n1, n2;
string s;
struct node{
	int id;
	int delta;
};
vector<node>A;
vector<node>B;

bool comp1(node &a, node &b){// 升序排序 
	if(a.delta!=b.delta)return a.delta<b.delta;// 优先根据增值排序，再根据字典序排序 
	return a.id<b.id;
}

bool comp2(node &a, node &b){// 降序排序 
	if(a.delta!=b.delta)return a.delta>b.delta;// 优先根据增值排序，再根据字典序排序 
	return a.id<b.id;
}

int main() {
	cin>>n1>>n2;
	for(int i=1;i<=n1;++i){
		int tmp;
		cin>>tmp, A.push_back({i, tmp});
	}
	for(int i=1;i<=n2;++i){
		int tmp;
		cin>>tmp, B.push_back({i, tmp});
	}
	sort(A.begin(), A.end(), comp1);// 升序排序 
	sort(B.begin(), B.end(), comp2);// 降序排序 
	cin>>s;
	int indexA = 0, indexB = 0;
	for(int i=0;i<s.size();++i){
		if(s[i]=='1'){
			cout<<"B"<<B[indexB++].id<<endl;
		}else{
			cout<<"A"<<A[indexA++].id<<endl;
		}
	}
	cout<<"E";
	return 0;
}

6、最少硬币问题

题目：

完成时间：2023年4月3日

tags：动态规划

$\textcolor{red}{分析：}$

状态转移方程：dp[j] = min(dp[j], dp[j-price[i]]+1);
别忘了初始化dp[0] = 0；

解决代码：

#include<bits/stdc++.h>
using namespace std;

int n;// 输入支付的金额 

int solve(int n){
	vector<int>price = {1, 2, 4, 5, 6};
	vector<int>dp(n+1, INT_MAX);// 动规求最小值
	dp[0] = 0;// 初始化 
	for(int i=0;i<5;++i){
		for(int j=price[i];j<=n;++j){
			dp[j] = min(dp[j], dp[j-price[i]]+1);// 求最小硬币数量 
		}
	}
	return dp[n]; 
}

int main() {
	cin>>n;
	int res = solve(n);
	cout<<res;
	return 0;
}

7、小明的背包 1

lanqiao-1174：第十四届蓝桥杯省赛冲刺营【第二期】 - 【课后练习】小明的背包 1 - 蓝桥云课 (lanqiao.cn)

完成时间：2023年4月3日

tags：动态规划、01-背包问题

$\textcolor{red}{分析：}$

经典的01-背包问题；
采用滚动数组进行空间压缩时需要注意重量j从大到小遍历；

解决代码：

#include<bits/stdc++.h>
using namespace std;

const int N = 1e3+10;// V<=1000
int n, V;
int dp[N];

int main() {
	cin.tie(0);
	cout.tie(0);
	cin>>n>>V;
//	for(int i=0;i<n;++i)cout<<dp[i]<<" ";cout<<endl;// dp默认初始化为全0 
	int w, v;
	for(int i=0;i<n;++i){
		cin>>w>>v;// 分别为体积和价值
		for(int j=V;j>=w;--j){
			dp[j] = max(dp[j], dp[j-w]+v); 
		} 
	}
	cout<<dp[V];
	return 0;
}

Copyright： Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.

每日一题

1、跳石头

2、完全背包问题

3、多重背包问题 I

4、 快乐司机

5、防御力

6、最少硬币问题

7、小明的背包 1

4、快乐司机