题目链接：https://ac.nowcoder.com/acm/contest/5668/E
题目大意：
给出一个序列定义一个序列的权值为：
问第一小和第二小的序列的权值和
其中对p有要求：
并且第一小与第二小的排列任何位置都不相同。
题目思路：
根据
i在全排列中的位置是pi，pi又在第i个位置
所以这个全排列的性质是 每两个元素之间进行了交换
也就说题目所要求的权值转换成为将序列分成N/2组每组的差值的绝对值最小
那么第一小绝对是排序后相邻两元素的差值和(没有一种差值比这小了)
第二小呢？
第二小会考虑到一些问题，题目中指出第一小与第二小的排列任何位置都不相同，那么就是说我们需要在排序之后打乱所有的顺序。也就是说在排序后继续做n/2次交换，使得相邻差值和最小。
此时有个结论：由于4和6可以把偶数都表示出来了，并且权值进行交换的话，写规律可以发现等于8的时候拆成2个4，比拆成1个8好，或者说8的最优情况其实就是2个4，由此可得10的话 就是 6 与 4，12就是...
这样就会发现很像背包的dp
所以只需要计算一下6个数交换的最小值与四个数交换的最小值即可。
Code：
/*** keep hungry and calm CoolGuang!***/
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<string.h>
#include<iostream>
#define rep(i,n) for(int i=1;i<=(n);i++)
#define debug(x) cout<<#x<<":"<<x<<endl;
#define _CRT_SECURE_NO_WARNINGS
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#pragma GCC option("arch=native","tune=native","no-zero-upper")
#pragma GCC target("avx2")
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pp;
const ll INF=1e17;
const int Maxn=2e7+10;
const int maxn =2e5+10;
const int mod=998244353;
const int Mod = 1e9+7;
const double eps=1e-3;
inline bool read(ll &num)
{char in;bool IsN=false;
in=getchar();if(in==EOF) return false;while(in!='-'&&(in<'0'||in>'9')) in=getchar();if(in=='-'){ IsN=true;num=0;}else num=in-'0';while(in=getchar(),in>='0'&&in<='9'){num*=10,num+=in-'0';}if(IsN) num=-num;return true;}
ll n,m,p;
map<ll,int>mp;
ll num[maxn],cop[maxn];
ll dp[maxn];
ll cal(int x,int y){
return min((cop[y]-cop[y-2]+cop[y-1]-cop[x])*2,(cop[y]-cop[x]+cop[y-1]-cop[y-2])*2);
}
ll cal_1(int x,int y){
return cop[y]+cop[y-1]-cop[y-2]-cop[y-3];
}https://ac.nowcoder.com/acm/contest/5668#submit/{%22onlyMyStatusFilter%22%3Atrue%2C%22problemIdFilter%22%3A%22209387%22}
ll cal_2(int x,int y){
ll tempa = cop[y]+cop[y-1]+cop[y-3]-cop[y-2]-cop[y-4]-cop[y-5];
ll tempb = cop[y]+cop[y-1]+cop[y-2]-cop[y-3]-cop[y-4]-cop[y-5];
return min(tempa,tempb);
}
int main(){
int T;scanf("%d",&T);
while(T--){
read(n);
for(int i=1;i<=n;i++){
read(num[i]);
cop[i] = num[i];
}
sort(cop+1,cop+1+n);
ll ans = 0;
for(int i=1;i<=n;i+=2)
ans += 2*abs(cop[i+1]-cop[i]);
dp[0] = 0 ;
for(int i=4;i<=n;i+=2){
dp[i] = INF;
if(i-4 == 0||i-4>=4)
dp[i] = min(dp[i],dp[i-4]+cal_1(i-3,i));
if(i-6 == 0||i-6>=4)
dp[i] = min(dp[i],dp[i-6]+cal_2(i-5,i));
}
printf("%lld\n",ans/2+dp[n]);
}
return 0;
}
/**
0 1 1 1 1 1
0 1 0 1 1 1
0 1 0 1 1 1
**/
京公网安备 11010502036488号