【算法通关指南：算法实战篇（五）】 --- 1.最长递增，2.交换瓶子，3.翻硬币》

小龙报

发布于 2025-12-15 15:57:44

1630

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

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

前言

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

一、最长递增

1.1题目：

题目链接：最长递增

1.2算法原理

这道题考点是模拟，我们通过遍历用一个变量len来记录合法区间的长度，当遍历的不合法的元素时利用一个变量ret来更新结果注：此题最小合法区间长度为1，当我们每次找到一个合法区间，在寻找下一个区间应把len更新为1

1.3代码

#include <iostream>
using namespace std;
const int N = 1e4 + 10;
int a[N],n;

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

	for (int i = 1; i <= n; i++)
		cin >> a[i];
	
	int len = 0; 
	int ret = 0;
	for(int i = 1;i <= n;i++)
	{	
		if (a[i] > a[i - 1])
			len++;
		else
		{
			ret = max(ret, len);
			len = 1; //一个元素也是一个合法区间
		}
	}

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

二、交换瓶子

2.1题目：

题目链接：交换瓶子

2.2算法原理

由于瓶子是有序的1~N，所以下标是1的位置就应该放1号瓶子，以此类推想到一种解法：遍历数组，当编号与放置位置不一致时，便将a[i]与a[a[i]]交换直至 a[i] == i

2.3代码

#include <iostream>
using namespace std;
const int N = 1e4 + 10;
int a[N];


void Swap(int a[], int i, int j)
{
	int temp = a[i];
	a[i] = a[j];
	a[j] = temp;
}

int main()
{
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];

	int ans = 0; //记录交换次数
	for (int i = 1; i <= n; i++)
	{
		while (a[i] != i)
		{
			ans++;
			Swap(a, i, a[i]);
		}
	}

	cout << ans << endl;
	return 0;
}

三、翻硬币

3.1题目：

题目链接：翻硬币

3.2算法原理

贪心策略：从左到右遍历，遇到不同的位置就翻转当前和下一个硬币。正确性证明：每个位置只能被前面的操作影响一次，必须立即修正差异，无法回溯。

3.3代码

#include <iostream>
using namespace std;

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

	int ans = 0;
	for (int i = 0; i < a.size(); i++)
	{
		if (a[i] != b[i])
		{
			a[i + 1] = a[i + 1] == 'o' ? '*' : 'o';
			ans++;
		}
	}

	cout << ans << endl;
	return 0;
}

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

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

原理