[常州市赛 2023] 洗牌

Luogu
IDLGB4220
Time1000ms
Memory512MB
DifficultyP3
贪心2023江苏排序科创活动小学活动
小 X 有 $n$ 张标有数字的纸牌,第 $i$ 张纸牌上面的数是 $a_i$,现在小 X 想通过洗牌打乱它们的顺序。 对于一个洗牌后的顺序,小 X 觉得相邻两张纸牌上数的差的绝对值之和越大,牌就洗的 越乱。 举个例子:现在有 $4$ 张纸牌,纸牌上的数依次为 $[1,2,3,4]$。 假设洗完牌后,纸牌上的数依次 $[4,3,2,1]$,相邻两张纸牌上数的差的绝对值之和为 $\left|4-3\right|+\left|3-2\right|+\left|2-1\right|=1+1+1=3$。 假设洗完牌后,纸牌上的数依次 $[2,4,1,3]$,相邻两张纸牌上数的差的绝对值之和为 $\left|4-2\right|+\left|4-1\right|+\left|3-1\right|=2+3+2=7$。 那么小 X 就会觉得 $[2,4,1,3]$ 的顺序比 $[4,3,2,1]$ 更乱。 小 X 想要问问你,对于所有顺序,相邻两张纸牌上数的差的绝对值之和最大能是多少。 ## Input 第一行 $1$ 个正整数 $n$,表示纸牌的张数。 第二行 $n$ 个正整数 $a_i$,表示第 $i$ 张纸牌上的数。注意具有相同数字的纸牌可能有多张。 ## Output 输出一行一个整数,表示答案。 [samples] ## Background 搬运自 <http://czoj.com.cn/p/677>。数据为民间数据。 ## Note 本题共有 $11$ 个测试点。 保证当测试点编号是偶数时,$n$ 也是偶数。 |测试点编号|$n$|$a_i$| |:-:|:-:|:-:| |$1\sim3$|$1\le n\le 10$|$1\le a_i\le10^6$| |$4\sim8$|$1\le n\le 100$|$1\le a_i\le 10$| |$9\sim11$|$1\le n\le10^5$|$1\le a_i\le 10^6$|
Samples
Input #1
4 
1 2 3 4
Output #1
7
Input #2
5
1 2 3 4 5
Output #2
11
Input #3
10
1 2 3 4 5 6 7 8 9 10
Output #3
49
API Response (JSON)
{
  "problem": {
    "name": "[常州市赛 2023] 洗牌",
    "description": {
      "content": "小 X 有 $n$ 张标有数字的纸牌,第 $i$ 张纸牌上面的数是 $a_i$,现在小 X 想通过洗牌打乱它们的顺序。 对于一个洗牌后的顺序,小 X 觉得相邻两张纸牌上数的差的绝对值之和越大,牌就洗的 越乱。 举个例子:现在有 $4$ 张纸牌,纸牌上的数依次为 $[1,2,3,4]$。 假设洗完牌后,纸牌上的数依次 $[4,3,2,1]$,相邻两张纸牌上数的差的绝对值之和为 $\\left|4",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB4220"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "小 X 有 $n$ 张标有数字的纸牌,第 $i$ 张纸牌上面的数是 $a_i$,现在小 X 想通过洗牌打乱它们的顺序。\n\n对于一个洗牌后的顺序,小 X 觉得相邻两张纸牌上数的差的绝对值之和越大,牌就洗的 越乱。\n\n举个例子:现在有 $4$ 张纸牌,纸牌上的数依次为 $[1,2,3,4]$。\n\n假设洗完牌后,纸牌上的数依次 $[4,3,2,1]$,相邻两张纸牌上数的差的绝对值之和为 $\\left|4...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments