牛客真题编程——day1

发布时间：2022-08-18 18:47

环境：c++

1、连续最大和

一个数组有 N 个元素，求连续子数组的最大和。例如：[-1,2,1]，和最大的连续子数组为[2,1]，其和为 3

首先使用穷举法，嵌套循环遍历出最大和，但是时间复杂度为n2，会有一个测试用例运行超时。

采用动态规划思想：

分解问题为：sum(最大和)+a[i]

否则 sum+=a[i]

2、搬圆桌

现在有一张半径为r的圆桌，其中心位于(x,y)，现在他想把圆桌的中心移到(x1,y1)。每次移动一步，都必须在圆桌边缘固定一个点然后将圆桌绕这个点旋转。问最少需要移动几步。

算法思想：

根据题意画图，可知任意选择圆上一点画图，则圆心可移动范围为：初始圆心为圆心，r=2r的大圆内。且要想最少次数移动到(x1,y1)，则移动方向只能为两圆心的连线。所以只需要求得最短距离和2r的倍数关系即可，余数自动舍入，结果即为移动步数。

需注意输入范围：一行五个整数r,x,y,x1,y1(1≤r≤100000,-100000≤x,y,x1,y1≤100000)

采用longlongint声明整型

3、最大乘积

给定一个无序数组，包含正数、负数和0，要求从中找出3个数的乘积，使得乘积最大，要求时间复杂度：O(n)，空间复杂度：O(1)

算法思想：题目要求时间复杂度n，所以不能用排序。其次需要对情况分类：当都为正数/负数时，选最大三值；当正负数同时存在时，需要max(最大正和两个最小负数，两个最大正数和一个最大负数)其一。

实现：INT_MIN，INT_MAX声明，循环判断输入i，排序出前三大，和两个最小。

输出：