Two Matchings

对于第一小,排序,然后求两个的差,即数组在(1,2)(3,4)......下标的差
对于第二小,还是排序,那么下来选4个数来进行(1,3)(2,4),但是可能会剩两个,所以对于每一个地方,只是4个不行,而是4个或6个来判断那个最小
6个的判断是(1,3)(2,5)(3,6)
然后对于第二种来写dp式子

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int t;
int n;
struct node
{
    ll v,id;
 } a[200005];
int cmp(node & a,node & b)
{
    return a.v<b.v||a.v==b.v&&a.id<b.id;     
}
ll dp[200005];
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%lld",&a[i]);
            a[i].id=i;
        }
        for(int i=1;i<=n;i++) dp[i]=2e10;
        sort(a+1,a+1+n,cmp);
        ll sum=0;      
        for(int i=2;i<=n;i+=2)
        {
            sum+=abs(a[i].v-a[i-1].v)   ;

        }

        for(int i=0;i<=n;i++)
        {
            if(i+4<=n) dp[i+4]=min(dp[i+4],dp[i]+a[i+4].v-a[i+1].v);
            if((i+6)<=n)
            {
                dp[i+6]=min(dp[i+6],dp[i]+abs(a[i+6].v-a[i+1].v));
            }

        }

        sum+=dp[n];
        printf("%lld\n",dp[n]*2);
    }
}