【算法通关指南：算法实战篇（四）】--- 1.数学老师的第一课，2.花坛》

小龙报

发布于 2025-12-15 15:29:16

240

文章被收录于专栏：C\C++C\C++

🔥小龙报：个人主页 🎬作者简介：C++研发，嵌入式，机器人方向学习者 ❄️个人专栏：《算法通关指南》 ✨ 永远相信美好的事情即将发生

前言

本专栏聚焦算法题实战，系统讲解算法模块：以《c++编程》，《数据结构和算法》《基础算法》《算法实战》等几个板块以题带点，讲解思路与代码实现，帮助大家快速提升代码能力 ps:本章节题目分两部分，比较基础笔者只附上代码供大家参考，其他的笔者会附上自己的思考和讲解，希望和大家一起努力见证自己的算法成长

二、课本分配

2.1题目

题目链接：课本分配

2.2算法原理

这道题的策略是先对两个数组进行排序（从大到小或者从小到大都可以），已从小到大为例，取最大知识量与知识接受上限量最大的同学匹配，不符合就取次大的知识量去匹配，依次类推，问题：（1）如何进行匹配答：定义两个指针i和j,分别指向已排序好的v和s的数组末尾，如果值相匹配就i–，j–否则取次大的知识量匹配就只要i–

2.3代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
typedef long long LL;
LL v[N], s[N];

int main()
{
	int n, m;
	cin >> n >> m;

	for (int i = 1; i <= n; i++)
		cin >> v[i];
	for (int i = 1; i <= m; i++)
		cin >> s[i];

	sort(v + 1, v + 1 + n);
	sort(s + 1, s + 1 + m);

	int i = n,j = m;
	LL sum = 0;
	while (i >= 1 && j >= 1)
	{
		if (v[i] <= s[j])
		{
			sum += v[i];
			i--;
			j--;
		}
		else
			i--; //寻找次大的
	}

	cout << sum << endl;
	return 0;
}

二、花坛

2.1题目

题目链接：花坛

2.2算法原理

这道题我们首先想到的是暴力枚举但这样一定会超时，题目的题眼很明确请你摘走一个区间的花，使得其中有至少 A个红花和 B 个黄花，并最小化白花的数量，那我们便可以使用双指针算法来优化。双指针双指针算法五步： 1.定义变量和维护窗口信息：两个变量l和r,使用一个哈希数组mp：维护窗口内abc的数量 2.进窗口：r移动mp[x[r]]++即可 3.调整窗口 + 更新结果：当满足mp[1] >= a && mp[2] >= b时，更新当前结果，并移动l变量调整mp寻找更优的合法窗口 5.出窗口：在移动l时，mp[x[l]]–

2.3代码

#include <iostream>
using namespace std;
const int N = 1e7 + 10;
int x[N];
int mp[N]; //记录区间abc的数量

int main()
{
	int n, a, b;
	cin >> n >> a >> b;

	for (int i = 1; i <= n; i++)
		cin >> x[i];

	int l = 1, r = 1;
	int ret = 1e7; //结果
	while (r <= n)
	{
		mp[x[r]]++; //进窗口
		while (mp[1] >= a && mp[2] >= b)
		{
			ret = min(ret, mp[0]); //更新结果

			mp[x[l++]]--; //调整窗口 + 出窗口
		}
		r++;
	}

	cout << ret << endl;
	return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-11-29，如有侵权请联系 cloudcommunity@tencent.com 删除

指针