目录

翻滚吧牛牛(一)

链接：https://ac.nowcoder.com/acm/contest/6776/A
来源：牛客网

牛牛有一个边长为1的正六边形，只要牛牛一推它就可以一直滚下去，正六边形左下角为A，牛牛想知道正六边形翻滚k次A点的轨迹边长是多少呢。如图是正六边形翻滚一次的情况。给定正六边形翻滚次数k，求A点翻滚轨迹长度

示例

输入：3
输出：4.955392

思路1

弧长公式为：n × π × r/180，其中n为弧线对应角度值，r为半径。在例图中只画出第一次翻滚的例子，该例子中弧线对应角度为60°，半径为1。

下面再给出翻滚第2次和第3次的例子，思路就很明显了。第2次翻滚，角度值依然为60°，半径为$\sqrt{3}$；第3次翻滚，角度值依然为60°，半径为2。

每翻滚6次为一个循环，每次翻滚角度皆为60°，所以求出这6次的半径，套入弧长公式求出每次翻滚的弧长，模6实现循环，累加起来即可。

代码1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

import math
 
class Solution:
    def circumference(self , k):
        r = [1, 3**0.5, 2, 3**0.5, 1, 0]
        hu = []
        for i in range(6):
            hu.append(60*math.pi*r[i]/180)
        res = 0
        for i in range(1, k+1):
            res += hu[i % 6 - 1]
        return res

牛牛的分配

链接：https://ac.nowcoder.com/acm/contest/6776/B
来源：牛客网

在牛牛面前有nn个瓶子，每个瓶子的大小体积都一样，但是每个瓶子内的含水量都不相同。 因为牛牛是个完美主义者，他希望瓶子中的水能够满足他的要求，他的要求是瓶子中的水最少为xx。所以他打算对这些瓶子里的水进行重新分配，以满足最多的瓶子中水量大于等于xx。 牛牛的分配规则是：每次可以选择多个瓶子，将里面的水平均分配到已选择的瓶子中。 给定nn个瓶子和牛牛的对瓶中的水量要求xx，以及nn个瓶子中的含水量，求最多可以有多少个瓶子满足牛牛的要求？

示例

输入：3,7,[9,4,9]
输出：3

思路1

贪心：先排序，先拿水多的瓶子，累加瓶子个数和水量，当瓶子个数乘以平均水量要求小于累计水量时，说明当前瓶子中的水量已经严重拖后腿，已拉低平均值到要求水量以下，故减去将平均值拉低至要求值以下的那瓶水瓶子个数，剩下的累计瓶子数即为所求。

代码1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

# 返回重新分配后，满足牛牛要求的水量的瓶子最多的数量
# @param n int整型 瓶子的数量
# @param x int整型 牛牛的对瓶中的水量要求
# @param a int整型一维数组 每个瓶子中的含水量
# @return int整型

class Solution:
    def solve(self , n , x , a ):
        # write code here
        res, sum = 0, 0
        a.sort()
        for i in range(n-1, -1, -1):
            sum += a[i]
            res += 1
            if sum < x * res:
                res -= 1
                break
        return res

牛牛构造等差数列

链接：https://ac.nowcoder.com/acm/contest/6776/C
来源：牛客网

牛牛和牛妹在玩一个游戏，在他们面前有n个数，他们对每个数可以进行 +1 或 -1 操作，但对于每一个数，该操作最多只能执行一次。 游戏胜利的目标是：使用最少的操作次数，将这几个数构造成一个等差数列。 牛牛特别想赢得游戏，所以他想让你帮他写一个程序，得出最少多少次操作后能使这几个数变成一个等差数列，当然，如果完全不能构造成功，就输出-1。

示例

输入：4,[24,21,14,10]
输出：3
说明：在第一个例子中，牛牛应该对第一个数字+1，对第二个数字-1，对第三个数字+1，而第四个数字应该保持不变。最后，序列就变成了[25,20,15,10]，这是一个等差数列且操作次数最少。

思路1

等差数列+智力：由前两项求等差，共九种情况，即第一项有加、减、不变3种，搭配第二项加、减、不变3种。由这9种情况的等差，从第三项开始逐项验证，每一项都由前一项通过加上等差所得，与给定数组对比。如果绝对差值小于等于1，则可以通过加、减操作或不变来实现等差构造；否则无法构造等差，终端循环。如果循环可以完成，则说明可以构造成等差数列，记录此时的结果，去所有可完成循环的结果的最小值，即为所求。

代码1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

# 返回最少多少次操作后能使这几个数变成一个等差数列，如果完全不能构造成功，就返回-1
# @param n int整型 代表一共有n个数字
# @param b int整型一维数组 代表这n个数字的大小
# @return int整型

class Solution:
    def solve(self , n , b ):
        # write code here
        if n <= 2:
            return 0
        b.sort()
        res = float("inf")
        for i in [-1, 0, 1]:
            for j in [-1, 0, 1]:
                fst = b[0] + i
                snd = b[1] + j
                step = snd - fst
                cur = snd
                cnt = abs(i) + abs(j)
                for k in range(2, n):
                    cur += step
                    if abs(cur - b[k]) <= 1:
                        cnt += abs(cur - b[k])
                    else:
                        break
                    if k == n-1:
                        res = min(res, cnt)
        return res if res < float("inf") else -1