A23492. 洗牌小X有n个张牌，每张第i张牌上面的数是a[i]，现在小X想打乱它们的顺序。对于一个洗牌后的顺序，小X觉得相邻两张牌上数的差的绝对值之和越大，牌就洗的越乱。举个例子：现在有4张牌，牌上的数依次为1,2,3,4。假设洗完牌后，牌上的数依次4,3,2,1，相邻两张牌上数的差的绝对值之和为|4-3|+|3-2|+|2-1|=1+1+1=3。假设洗完牌后，牌上的数依次2,4,1,3，相邻两张牌上数的差…
填空题
中等
知识点
题目描述
洗牌
小X有n个张牌，每张第i张牌上面的数是a[i]，现在小X想打乱它们的顺序。
对于一个洗牌后的顺序，小X觉得相邻两张牌上数的差的绝对值之和越大，牌就洗的越乱。
举个例子：现在有4张牌，牌上的数依次为1,2,3,4。
假设洗完牌后，牌上的数依次4,3,2,1，相邻两张牌上数的差的绝对值之和为|4-3|+|3-2|+|2-1|=1+1+1=3。
假设洗完牌后，牌上的数依次2,4,1,3，相邻两张牌上数的差的绝对值之和为|4-2|+|4-1|+|3-1|=2+3+2=7。
那么小X就会觉得2,4,1,3的顺序比4,3,2,1更乱。
小X想要问问你，对于所有顺序，相邻两张牌上数的差的绝对值之和最大能是多少。
输入
第一行1个正整数n，表示牌的个数。
第二行n个正整数a[i]，表示第i张牌上的数字。
输出
输出一行一个整数，表示答案。
样例输入1
4
1 2 3 4样例输入2
5
1 2 3 4 5样例输入3
10
1 2 3 4 5 6 7 8 9 10样例输出1
7样例输出2
11样例输出3
49提示
样例解释2
一种可行的顺序是3 5 1 4 2
数据范围
保证当测试点编号是偶数时，n也是偶数。
对于测试点1-3：1<=n<=10, 1<=a[i]<=1000000
对于测试点4-8：1<=n<=100, 1<=a[i]<=10
对于测试点9-11：1<=n<=100000, 1<=a[i]<=1000000
参考答案
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
sort(a.begin(), a.end());
// 分两部分：小半部分和大半部分
vector<int> small, large;
for (int i = 0; i < n; ++i) {
if (i < n / 2) small.push_back(a[i]);
else large.push_back(a[i]);
}
// 交叉合并（小-大-小-大...）
vector<int> res;
int s = 0, l = 0;
bool flag = true; // 先取小半部分
while (s < small.size() || l < large.size()) {
if (flag && s < small.size()) {
res.push_back(small[s++]);
} else if (l < large.size()) {
res.push_back(large[l++]);
}
flag = !flag;
}
// 计算相邻差之和
long long sum = 0;
for (int i = 1; i < res.size(); ++i) {
sum += abs(res[i] - res[i-1]);
}
cout << sum << endl;
return 0;
}
上一题
下一题