题目描述

最大排列差

现在有一个长度为 n 的排列 1, 2, 3, ... n，现在小满希望将这个排列重新排列，要求每个位置和原来的数字不同，且相同位置的差的绝对值的和最大

• 输入：一个整数n. 3 <= n <= 10^12
• 输出： 一个整数，答案对100000007取模

测试用例

用例1：

• 输入： 3
• 输出： 4
• 解释：1, 2, 3 重新排列得到 3, 1, 2，差为4

用例2：

• 输入： 5
• 输出： 12
• 解释：1, 2, 3, 4, 5 重新排列得到4, 5, 1, 2, 3，差为12

思路

因为是12345这种固定顺序，所以测几个用例发现，题目要求的最大值，排列顺序情况是一样的，和排列长度的奇偶有关系，同时发现得到的差的绝对值是有规律的

• 当排列长度为奇数时，得到的最优情况为 (n - 1)(n + 1) / 2
• 当排列长度为偶数时，得到的最优情况一定是1, 1, 3, 3, 5, 5, 7, 7... 这样的结果， 也就是 (n * n) / 2

代码实现

var __readline = require("readline-sync");
__readline.setDefaultOptions({ prompt: "" });
var readline = __readline.prompt;

console.log("请输入n: ");
let n = BigInt(readline());
console.log("n: ", n);
function test(n) {
  let sum = 0;
  if (n % BigInt(2) === 0n) {
    sum = ((n * n) / BigInt(2)) % BigInt(100000007);
  } else {
    sum = (((n - BigInt(1)) * (n + BigInt(1))) / BigInt(2)) % BigInt(100000007);
  }

  return sum;
}

console.log("结果为: ", Number(test(n)));