【算法通关指南：算法实战篇（二）】--- 1.连续因子，2.燃油交换

小龙报

发布于 2025-12-15 15:51:31

1660

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

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

前言

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

一、连续因子—2016年天梯赛

1.1 题目

1.2 算法原理

首先我们要明确我们要输出的是最小的连续因子序列，也就是如果有两端长度相同的序列取小的那一段就可以了

接下来我们要解决两个问题： （1） 如何找出这段序列：解：这个时候我们就可以借鉴求解一个数是否是素数的方式，既一个数x如果有两个因子a和b,那必然有一个因子是小于等于根号x的，那我们便可以遍历2到根号x来求解连续因子 (2) 如何输出这一段序列解：我们可以定义一个变量st每次求出一段序列便把序列头赋值给st，依照最后求出的长度使用一个for循环遍历输出就可以了

1.3 代码

#include <iostream>
#include <cmath>
using namespace std;

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

	//当n是合数时
	int st = 0; //记录序列头
	int ans = 0; //序列的最长长度
	for (int i = 2; i <= sqrt(n); i++)
	{
		int j = i;
		int len = 0; //当前连续序列的长度
		int result = 1;
		if (n % i == 0) 
		{
			while (1)
			{
				result *= j;
				if (n % result != 0) //不满足
					break;
				len++;

				if (ans < len) //序列长度相同取前面小的一段:更新长度 + 因子序列的开头
				{
					ans = len;
					st = i;
				}
				j++;
			}
		}
	}

	//如果n是质数
	if (ans == 0)
	{
		ans = 1;
		st = n;
	}

	cout << ans << endl;
	for (int i = 0; i < ans; i++)
	{
		if (i > 0)
			cout << "*";
		cout << st + i;
	}
	cout << endl;
	return 0;
}

二、燃油交换

2.1 题目：

链接：燃油交换

2.2算法原理

因为只能换一次燃料所以使用任何一种燃料必然是连续的，即先选a剩下的选b或者先选b剩下的选b,故我们可以枚举从1到n天使用a剩下的选b与1到n天使用b剩下的选a取一个最小值就可以了，我们可以使用前缀和记录【1，i】天a或b燃料的消耗情况

2.3代码

#include<iostream>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
LL a[N], b[N];
int main()
{
	int n;
	cin >> n;

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

	LL ret = 1e20;
	for (int i = 1; i <= n; i++)
	{
		LL sum = min(a[i] + (b[n] - b[i]), b[i] + (a[n] - a[i]));  
		ret = min(ret, sum);
	}

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

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

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

遍历