这道世纪难题，谁能用c++写

Question

题目描述
给定两个长度为
�
n的数组
�
,
�
a,b，其中数组
�
a由
1
,
3
,
5...
,
2
�
−
1
1,3,5...,2n−1这
�
n个奇数打乱顺序组成，数组
�
b由
2
,
4
,
6...
,
2
�
2,4,6...,2n这
�
n个偶数打乱顺序组成。你可以对这些数组执行以下操作：

将某个排列中相邻的两个元素交换位置。
问至少需要多少次操作，才能使得
�
a的字典序小于
�
b的字典序。

输入格式
第一行一个整数
�
(
1
≤
�
≤
10000
)
t(1≤t≤10000)表示测试用例的数量。 对于每个测试用例包含一个整数
�
(
1
≤
�
≤
1
0
5
)
n(1≤n≤10
5
)表示数组的长度。 每个测试用例第一行
�
n个数包含数组
�
a，第二行
�
n个数包含数组
�
b。

输出格式
对于每组测试用例，输出一个整数表示最少需要的操作次数。

样例
输入数据 1
3
2
3 1
4 2
3
5 3 1
2 4 6
5
7 5 9 1 3
2 4 6 10 8
输出数据 1
0
2
3
谁能做出来这道世纪难题

Answer 1

• 这个问题的回答你可以参考下: https://ask.csdn.net/questions/366684
• 除此之外, 这篇博客: 给你一根长度为n的绳子，请把绳子剪成整数长的m段，每段绳子的长度记为k[0],k[1],...,k[m]。请问k[0]xk[1]x...xk[m]可能的最大乘积是多中的 给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1），每段绳子的长度记为k[0],k[1],…,k[m]。请问k[0]xk[1]x…xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
  

• 解题过程：类比上述案例截图过程。则有
  1.分析题意:
  绳子长度为n，分成m分，那先设分后每份长度为x, 份数m=n/x
  那么结果就是 n/x个 x 相乘 f(x)=(n/x)(n/x)…*(n/x) = x^(n/x).

  因为maxMul = f(x) = x^(n/x);
  两边同时求对数，则有:ln(f(x)) = n/x(lnx);
  两边同时求导。则有：
  

  
  有上述求导过程可知。当x = 3时候。m = n/x有以下三种情况：

  1. f(x) = 3^n/3  n%3 ==0;
  2. f(x) = 3^(n/3-1)*4 n%3 ==1;
  3. f(x) = 3^(n/3)*2;
  

  注意：另外还需考虑绳子的长度小于3的情况。
  完整代码如下：

  public class Solution {
      public int cutRope(int target) {
          if(target == 2){return 1;}
          if(target == 3){return 2;}
          if(target >=4){
              if(target % 3 == 0){
                  return (int)Math.pow(3,target/3);
              }else if(target % 3 == 1){
                  return 4*(int)Math.pow(3,target/3 -1);
              }else{
                  return 2*(int)Math.pow(3,target/3);
              }
          }
          return 0;
      }
  }