首页 > 试题广场 >

多多的排列函数

[编程题]多多的排列函数
  • 热度指数：2707 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
数列 {An} 为N的一种排列。
例如N=3，可能的排列共6种： 
1, 2, 3
1, 3, 2
2, 1, 3
2, 3, 1
3, 1, 2
3, 2, 1
定义函数F:

其中|X|表示X的绝对值。

现在多多鸡想知道，在所有可能的数列 {An} 中，F(N)的最小值和最大值分别是多少。

输入描述:
第一行输入1个整数T，表示测试用例的组数。
( 1 <= T <= 10 )
第二行开始，共T行，每行包含1个整数N，表示数列 {An} 的元素个数。
( 1 <= N <= 100,000 )


输出描述:
共T行，每行2个整数，分别表示F(N)最小值和最大值
示例1

输入

2
2
3

输出

1 1
0 2

说明

对于N=3：
- 当{An}为3，2，1时可以得到F(N)的最小值0
- 当{An}为2，1，3时可以得到F(N)的最大值2

备注:
对于60%的数据有： 1 <= N <= 100
对于100%的数据有：1 <= N <= 100,000
算法知识视频讲解
添加回答
Python
想去东北泡澡的芝士在刷题头像 想去东北泡澡的芝士在刷题 
t = int(input())
def getmin(n):
    if n % 4 == 1 or n % 4 == 2:
        return 1
    if n % 4 == 3 or n % 4 == 0:
        return 0
for i in range(t):
    n = int(input())
    print(getmin(n), n - getmin(n - 1))
如上述大佬们的陈述，四个一组，因为n时候的最大值不大于n，又由于最小值只会取到0，1，所以最大值在n和n-1里面取是合理的。
编辑于 2020-08-08 14:01:05 回复(1)
Python
我不想当大白菜头像 我不想当大白菜

分析

对最小值的求解，当数组是上升或者下降的时候均满足，其值只能是1或者0,通过函数calc_min()直接计算。

最大值的求解，不能通过回溯去生成序列(时间复杂度太高),由函数F的公式：，要使得F(x)最大，即令F(x-1)最小，即N - calc_min(N-1)。

def calc_min(N):
    min_li = [i for i in range(N,0,-1)]
    res = min_li[0]
    for i in range(1,N):
        res = abs(res-min_li[i])
    return res

def calc_min_max(N):
    min_val = calc_min(N)
    max_val = N - calc_min(N-1)
    print("{} {}".format(min_val,max_val))

def main():
    T = int(input())
    for i in range(T):
        N = int(input())
        if N == 1:
            print("1 1")
        else:
            calc_min_max(N)
main()
发表于 2020-07-09 13:36:07 回复(0)
提交观点

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 前端工程师 算法工程师 PHP工程师 2020 拼多多 大数据开发工程师 Java工程师 信息技术岗
上传者：小小
难度：
2条回答 8666浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号