首页 > 试题广场 > 多多的排列函数
[编程题]多多的排列函数
  • 热度指数:1940 时间限制: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
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)
看了半天题目没看懂
发表于 2020-08-04 21:38:01 回复(1)

题目一开始没读懂,意思是:在{An}的所有排列中,能让F(N)取得的最大最小值为多少。

每四个数 例如 5,6,7,8,我们把它们两两一组 |||8-6|-7|-5|=0,最小值是0;猜测最小值的变化也是4个一组

看到min只有2种取值。0,1,最大值自然就是N-getmin(N-1)
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int nums = sc.nextInt();
        for (int i = 0; i<nums; i++){
            int N = sc.nextInt();
            maxandmin(N);
        }
    }
 
    public static void maxandmin(int N){
        if (N==1||N==2){
            System.out.println("1 1");
            return;
        }
        //之后每4个一组 0011
        int min = getmin(N);
        int max = N-getmin(N-1);
        System.out.println(min + " " + max);
    }
 
    public static int getmin(int N){
        int temp = (N-2)%4;
        if (temp==1 || temp==2){
            return 0;
        }
        else return 1;
    }
 
}


编辑于 2020-05-21 17:35:53 回复(9)
1.最小值看n%4的余数,余数为1或2时,取值为1,其他为0;
2.最大值相当于在1,2,...,n-1数列的一种最小值排列的右边再放一个n,所以最大值取值为Fmin-n;
#include <iostream>
#include <algorithm>

using namespace std;

int F[100001][2];
void getMinMax(int N){
    for(int i=1;i<=N;i++){
        if(i==1){
            F[1][0] = 1;
            F[1][1] = 1;
        }
        F[i][0] = (i%4 == 1 || i%4 == 2)? 1:0;
        F[i][1] = abs(F[i-1][0]-i);
    }
}

int main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        getMinMax(n);
        cout<<F[n][0]<<" "<<F[n][1]<<endl;
    }
    return 0;
}


发表于 2020-09-13 11:19:28 回复(0)
发表于 2020-05-31 22:03:28 回复(3)
import java.util.Scanner;
public class Main {
    public static void main(String[] args)
    {
       Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        for(int i=0;i<n;i++)
        {
            int N = scan.nextInt();
            System.out.println(min(N)+ " "+max(N));
        }
    }
     
    public static int min(int n)
    {
        if(n % 4 == 0 || (n+1) % 4 == 0)
        {
            return 0;
        }else
        {
            return 1;
        }
    }
     
    public static int max(int n)
    {
        if(n == 1)
        {
            return 1;
        }
        if(n == 2)
        {
            return 1;
        }
        return Math.abs(min(n-1)-n);
    }
}

发表于 2020-05-21 16:11:45 回复(4)
详细的解题思路以及代码可以参考我的博客http://39.108.236.169:8080/article/3
发表于 2020-05-26 23:58:40 回复(2)

这道题没啥意义,直接作弊吧。

#include 

using std::cin;
using std::cout;
using std::endl;

class An {
private:
    int m_max;
    int m_min;
    int m_N;

public:
    An(int n): m_N{n}, m_min{min(n)}, m_max{max(n)} {}
    int get_min() { return this->m_min; }
    int get_max() { return this->m_max; }

private:
    int min(int x) {
        if (x % 4 == 1 || x % 4 == 2) {
            return 1;
        }
        if (x % 4 == 3 || x % 4 == 0) {
            return 0;
        }
    }

    int max(int x) {
        return x - min(x - 1);
    }

};

int main(int argc, char** argv)
{
    int T;                      // 输入T位数字
    int N;                      // N 数列An的个数

    cin >> T;

    while(T-- != 0 && cin >> N) {
        An tmp{N};

        // 输出结果
        cout << tmp.get_min() << " " << tmp.get_max() << endl;
    }

    return 0;
}
发表于 2020-11-08 12:26:47 回复(0)







import java.util.Scanner;



public class Main 
{
    public static int find_Max(int n)
    {
        return n - find_Min(n-1);
        
    }
    public static int find_Min(int n)
    {
        int i = n-1;
        while(i >= 1)
            {
                n =Math.abs(n - i);
                i--;
            };
        return n;
    }
    
    
    public static void main(String[] args) 
    {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        for (int i = 1; i <= num; i++) 
        {
            int n = sc.nextInt();
            System.out.print(find_Min(n)+" ");
            System.out.println(find_Max(n));
        }
    
        
        
    }                    
}

发表于 2020-10-25 19:09:29 回复(0)
***我吧,看不懂公式
发表于 2020-09-26 18:35:12 回复(0)
#include <iostream>
#include <string>
#include <map>
#include <vector>

#include<algorithm>
#include <stdlib.h>
using namespace std;

int max(int i ,int j){
    
    return i > j? i:j;
}
//int abs(i){
//    
//    if i < 0
//        return -i;
//    else
//        return i;
//}
int main() {
    
    int N,i;
    cin >> N;
    
    int min[4] = {0,1,1,0};
    int xmin = N %4;
    cout<< min[xmin];
    vector<int> xmax;
    xmax.push_back(0);
    xmax.push_back(1);
    xmax.push_back(1);
    for(i = 3;i <= N;i++){
        
        xmax.push_back(max(abs(xmax[i-1] -i),abs(min[i %4 - 1] - i)));
        
    }
    
    cout<<xmax[N];
    

发表于 2020-09-05 10:57:01 回复(0)
找规律的题??
importjava.util.*;
publicclassMain{
    publicstaticvoidmain(String[] args){
        Scanner sc = newScanner(System.in);
        intT = sc.nextInt();
         
        for(inti = 0; i < T; i++){
            intN = sc.nextInt();
            intMin = Integer.MAX_VALUE; //存放最小值
            intMax = Integer.MIN_VALUE; //存放最大值
            
            if(N % 4== 1){
                System.out.println(1+" "+N);
            }elseif(N % 4== 2){
                System.out.println(1+" "+(N-1));
            }elseif(N % 4== 0){
                System.out.println(0+" "+N);
            }elseif(N % 4== 3){
                System.out.println(0+" "+(N-1));
            }
        }
        sc.close();
    }
}
发表于 2020-09-01 16:23:33 回复(0)
这是一个找规律的题,主要是找fmin
对于任意的4个连续自然数,k+3 k+2 k+1 k   fmin=0
s1 = 1|fmin=1
s2= 2 1|fmin=1
s3=3 2 1   |fmin=0  ( 这是特殊情况,亦可以理解为 3 2 1 0)
s4= 4 3 2 1 |fmin=0
在s1 s2 s3 s4 的基础上,加4个数字时,Fi+4(min)=Fi(min)
Fimax = i-F(i-1)min


发表于 2020-08-02 13:08:32 回复(0)
n = int(input().strip())
for i in range(n):
    num = int(input().strip())
    if num == 1&nbs***bsp;num==2:
        print(1, 1)
        continue
    if num%2:
        if ((num-1)//2)%2:
            pre_low = 1
        else:
            pre_low = 0
        high = num - pre_low
        if pre_low:
            low = 0
        else:
            low = 1
        print(low, high)
    else:
        if (num//2)%2:
            pre_low = 1
        else:
            pre_low = 0
        high = num - pre_low
        print(pre_low, high)

发表于 2020-08-02 10:49:05 回复(0)
这完全是数学题,不值得做!
发表于 2020-08-01 17:17:23 回复(0)
傻d题目出的完全看不懂你要考什么
发表于 2020-08-01 15:41:45 回复(1)
给上面第一个大神的解答

题目一开始没读懂,意思是:在{An}的所有排列中,能让F(N)取得的最大最小值为多少。

每四个数 例如 5,6,7,8,我们把它们两两一组 |||8-6|-7|-5|=0,最小值是0;猜测最小值的变化也是4个一组。看到min只有2种取值。0,1,最大值自然就是N-getmin(N-1)

我补充下解释

最大值\:N-Fn最小值
Fn的定义是(两两之差A)与(第三数B)之差C,然后迭代所有数。(1) 因为是作差运算,C肯定小于运算数里大的那一个,更会小于N(最大数)。(2) 所以F(x-1)<Ax,要让Fn最大,那么F(x-1)接近于0,Ax接近于An(即N)。(3) 最大值Fn_max = N-Fn_min.
最小值:只取0或1
数连续的时候好分析,每四个连续,数的Fn_min是0,0和下一个数E做差还等于下一个数E,从E开始再凑四个数,Fn计算又得0. (n<N)
假设剩下三个数,无法抵消到0;要让结果最小,则,总序列的末尾开始四个四个数地取走,剩下的最开始连续的三个数(1 2 3),F最小为0
假设剩下两个(1 2)、一个数(1),分析同上,F最小为1.
解释的也不太清楚,不过应该可以帮助理解了
发表于 2020-08-01 14:11:10 回复(0)

分析

对最小值的求解,当数组是上升或者下降的时候均满足,其值只能是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)
#include <iostream>
using namespace std;
 
int main(int argc, char* argv[]){
    int t, n;
    int arr1[] = {1, 1, 0, 0}, arr2[] = {0, -1, -1, 0};
    cin >> t;
    while(t--){
        cin >> n;
        cout << arr1[(n-1)%4] << " " << n+arr2[(n-1)%4] << endl;
    }
    return 0;
}

发表于 2020-07-02 12:34:12 回复(0)
def getmin(n):
    if n%4==0&nbs***bsp;n%4==3:
        return 0
    else:
        return 1
def getmax(n):
    return n-getmin(n-1)
if __name__ == "__main__":
    t = int(input())
    for i in range(t):
        n = int(input())
        print(getmin(n),getmax(n))

发表于 2020-06-03 17:19:11 回复(0)