2020牛客多校赛第三场

题目名称：E-Two Matching

来源：https://ac.nowcoder.com/acm/contest/5668/E

tag：动态规划,贪心

题意：p是一个matching，当且仅当所有合法的i满足 p[i]!=i && p[p[i]]==i ；求两个完全不等的matching p和q的代价(∑(i=1,n) abs(a[i]−a[p[i]])) / 2。

题解：

comment：赛中没发现是个环qwq

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cmath>
 4 #define _rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
 5 #define SF scanf
 6 #define PF printf
 7 const int N=200000;
 8 int t,n;
 9 long long f[N+3],a[N+3];
10 int main(){
11     SF("%d",&t);
12     while(t--){
13         SF("%d",&n);
14         _rep(i,1,n){
15             SF("%lld",&a[i]);
16         }    
17         std::sort(a+1,a+n+1);
18         f[2]=a[4]-a[1];
19         f[3]=a[6]-a[1];
20         f[4]=f[2]+a[8]-a[5];
21         for(int i=10;i<=n;i+=2){
22             f[i>>1]=std::min(f[(i-4)>>1]+a[i]-a[i-3],f[(i-6)>>1]+a[i]-a[i-5]);
23         }
24         PF("%lld
",(f[n>>1]<<1));
25     }
26     return 0;
27 }