2020牛客多校第三场 E Two Matchings

这道题目好像看到好多种做法

白话解释:就是类似两两交换,然后求与原来的差值的和最小,然后保证n>=4且是偶数
那就有点贪心的味道了,老贪心了,来来来 看看怎么构造使得绝对值的差最小,国际惯例遇到数组先sort,
然后看绝对值的贡献,不就是跨过的区间越小越好不是吗 然后就去算贡献了
代码:

#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ll long long
using namespace std;
const int INF=0x3f3f3f3f;
const double pi=acos(-1),eps=1e-8;
const int maxn=2e5+10;
ll a[maxn],dp[maxn];
int main()
{
//	ios::sync_with_stdio(false);
//	cin.tie(0);cout.tie(0);
	int t;
	scanf("%d",&t);
	while(t--){
		int n;
		scanf("%d",&n);
		for(int i=1;i<=n;i++){
			scanf("%lld",&a[i]);
		}
		sort(a+1,a+n+1);
		dp[4]=2*(a[4]-a[1]);
		dp[6]=2*(a[6]-a[1]);
		dp[8]=dp[4]+2*(a[8]-a[5]);
		for(int i=10;i<=n;i+=2){
			int x=dp[i-4]+2*(a[i]-a[i-3]);
			int y=dp[i-6]+2*(a[i]-a[i-5]);
			dp[i]=min(x,y);
		}
		printf("%lld\n",dp[n]);
	} 
 	return 0;
}

本文地址：https://blog.csdn.net/qq_43624815/article/details/107568008