首页 > 试题广场 >

多多的排列函数

[编程题]多多的排列函数
  • 热度指数:2696 时间限制: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

题目一开始没读懂,意思是:在{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)
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-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)
看了半天题目没看懂
发表于 2020-08-04 21:38:01 回复(1)
这是在考阅读理解吧
F(1)=A1
F(2) = |F(1)-A2| =|A1-A2|
F(3) = |F(2)-A3| =||A1-A2|-A3|
而 A1A2A3是 123的某种排列
当 [A1 A2 A3 ]=[3,2,1]时,带入上述公式 F(3)= ||3-2|-1|=|1-1|=0 ,是最小值
当 [A1 A2 A3 ] =[2,1,3]时,带入上述公式F(3)=||2-1|-3|=|1-3|=2, 是最大值


 



发表于 2021-04-27 14:15:01 回复(1)
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)
找规律的小游戏

import java.util.*;
public class Main{
    public static void main(String[] args){
        
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        for(int i=0;i<n;i++){
            int count=0;
            int a=sc.nextInt();
            if(a%4==1 || a%4==2){
                System.out.print(1);
            }else{
                System.out.print(0);
            }
            System.out.print(" ");
            if(a%4==1||a%4==0){
                System.out.print(a);
            }else{
                System.out.print(a-1);
            }
            
            System.out.println();
        }
        
    }
}

发表于 2022-04-10 18:17:33 回复(0)
给上面第一个大神的解答

题目一开始没读懂,意思是:在{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)
什么破题啊,怎么看怎么看不明白。An到底是个值还是个数列还是个矩阵啊???
编辑于 2024-03-23 21:40:26 回复(0)
const readline = require('readline')
const rl = readline.createInterface({
    input:process.stdin,
    output:process.stdout
})
let count = 0;
const getMin = function(n){
    return Math.ceil(n/2)%2
}
rl.on('line',(input) => {
    if(count > 0){
        let n = +input
        let min = getMin(n)
        let max = n - getMin(n-1)
        console.log(min,max)
    }
    count++
})

发表于 2022-04-10 11:05:34 回复(0)
t = int(input())
for _ in range(t):
    n = int(input())
    print((n + 1) // 2 & 1, end = ' ')
    print(n - (n // 2 & 1))

发表于 2022-04-08 23:54:12 回复(0)
回溯超时。
使用评论区大佬的思路:
将后面的4个一组消掉(差绝对值为0),再保留前面的0~3个数直接求解,得到最小值。
n的最大值就是n减去getMIn(n-1)的最小值
import java.util.*;    
public class Main {
    
     public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            for (int i = 0; i < n; i++) {
                int cur = sc.nextInt();
                int min = getMinSubstrctionAbs(cur);
                
                //留下最大值,然后去求剩下数字的最小值
                int max = cur - getMinSubstrctionAbs(cur - 1);
                System.out.println(min + " " + max);
            }
            sc.close();
        }

        /**
         * @return 获取[1, n]这些数的组合的最小绝对值
         */
        private static int getMinSubstrctionAbs(int n) {
            if (n == 1 || n == 2) {
                return 1;
            } else if (n == 0 || n == 3) {
                return 0;
            }
            //将后面的4个一组消为0
            n %= 4;
            //取前 n - 4 * ?个值计算最小绝对值
            return getMinSubstrctionAbs(n);
        }
    
    
        public static void main1(String[] args) {
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            for (int i = 0; i < n; i++) {
                int cur = sc.nextInt();
                min = Integer.MAX_VALUE;
                max = 0;
                int[] nums = new int[cur];
                for (int j = 1; j <= cur; j++) {
                    nums[j - 1] = j;
                }
                dfs(nums);
                System.out.println(min + " " + max);
            }
            sc.close();
        }

        private static int min, max;

        private static void dfs(int[] nums) {
            int n = nums.length;
            if (n == 1) {
                max = Math.max(nums[0], max);
                min = Math.min(nums[0], min);
                return;
            }
            
            //选出两个数求差的绝对值
            int[] tmp = new int[n - 1];
            for (int i = 0; i < n - 1; i++) {
                for (int j = i + 1; j < n; j++) {
                    int idx = 0;
                    for (int k = 0; k < n; k++) {
                        if (k != i && k != j) {
                            tmp[idx++] = nums[k];
                        }
                    }
                    tmp[idx] = Math.abs(nums[i] - nums[j]);
                    dfs(tmp);
                }
            }
        }

    }

发表于 2022-03-26 16:07:02 回复(0)
比较容易想到的是f(n)最大值可以把n放最后,这样前面选择f(n-1)的最小值即可。
然而最小值的规律并不具有递推特性,一种可行的方案是把1放最后,然后其他n-1个数字进行操作,尽可能得到绝对值较小的数字。
进一步想到用相邻数字依次做减法,那么答案只可能出现0,1,2这3个数字,可以分析n%4==0 和n%4==3最小值是0,其他情况最小值是1.
既然有了最小值公示,最大值自然可以推得。
#include <iostream>

using namespace std;
int n,t;
int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n;
        if(n<=2)
         cout<<"1 1"<<endl;
        else if(n%4==0)
              cout<<"0 "<<n<<endl;
        else if(n%4==3)
              cout<<"0 "<<n-1<<endl;
        else if(n%4==1)
             cout<<"1 "<<n<<endl;
        else
            cout<<"1 "<<n-1<<endl;
    }
    return 0;
}




发表于 2021-10-27 15:47:32 回复(0)

全排列模拟,根据部分结果找规律

  • F(N)指的是一个排列中的该函数的最后一项,比如N=3时的一个排列是:{3,2,1}, 则F(1)=3,F(2)=1,F(3)=1, 这个F(3)就是F(N)
import java.util.Scanner;
public class Main {
    public static void printMinAndMax(int N) {
        int min = 0;
        int max = 0;
        if (N % 4 == 0) {
            max = N;
        } else if (N % 4 == 3) {
            max = N - 1;
        } else if (N % 4 == 2) {
            min = 1;
            max = N - 1;
        } else {
            min = 1;
            max = N;
        }
        System.out.println(min + " " + max);
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();
        for (int i = 0; i < T; i++) {
            printMinAndMax(scanner.nextInt());
        }
    }
}

证明过程(只看解法有点莫名其妙)

public class Main {  
    /*
        运行部分结果
        N= 2时, min= 1, max= 1   min=1,max=N-1
        N= 3时, min= 0, max= 2     min-0,max=N-1
        N= 4时, min= 0, max= 4        min=0,max=N
        N= 5时, min= 1, max= 5 min=1,max=N
        N= 6时, min= 1, max= 5   min=1,max=N-1
        N= 7时, min= 0, max= 6     min=0,max=N-1
        N= 8时, min= 0, max= 8        min=0,max=N
        N= 9时, min= 1, max= 9 min=1,max=N
        N=10时, min= 1, max= 9   min=1,max=N-1
        N=11时, min= 0, max=10     min=0,max=N-1
        N=12时, min= 0, max=12        min=0,max=N
        // 基本一目了然了
     */
    public static void main(String[] args) {
        for (int N = 2; N <= 12; N++) { // 跑到15左右就要挺久了...足够找到规律了
            int[] arr = new int[N + 1];
            for (int i = 1; i < arr.length; i++) {
                arr[i] = i;
            }
            FNMin = Integer.MAX_VALUE;
            FNMax = Integer.MIN_VALUE;
            quanpailie(arr, 1);
            System.out.printf("N=%2d时, min=%2d, max=%2d\n", N, FNMin, FNMax);
        }
    }
    private static int FNMin = Integer.MAX_VALUE;
    private static int FNMax = Integer.MIN_VALUE;
    // 全排列
    public static void quanpailie(int[] arr, int currentIndex) {
        if (currentIndex >= arr.length) {
            calculate(arr);
            return;
        }
        for (int i = currentIndex; i < arr.length; i++) {
            swap(arr, currentIndex, i);
            quanpailie(arr, currentIndex + 1);
            swap(arr, currentIndex, i); // 回溯
        }
    }
    public static void calculate(int[] arr) {
        int Fx = arr[1]; // F(1) = A1
        for (int i = 2; i < arr.length; i++) { // F(x)=F(x-1)-Ax
            Fx = Math.abs(Fx - arr[i]);
        }
        FNMin = Math.min(Fx, FNMin);
        FNMax = Math.max(Fx, FNMax);
    }
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
编辑于 2021-07-20 02:12:39 回复(0)

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

#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)