公平划分

#include <bits/stdc++.h>
using namespace std;

int n, m, Min=INT_MAX;

void F(int *a, vector<int> t, int d, int num){
    if(num==m){
        vector<int> v;
        set<int> s;
        for(int i=0;i<m;i++)
            s.insert(t[i]);
        for(int i=0;i<n;i++){
            if(s.find(a[i]) != s.end())
                s.erase(a[i]);
            else
                v.push_back(a[i]);
        }
        int sum = 0;
        for(int i=0;i<t.size();i++)
            for(int j=0;j<v.size();j++)
                sum += abs(t[i]-v[j]);
        Min = min(Min, sum);
        return;
    }
    for(int j=d;j<n;j++){
        t.push_back(a[j]);
        F(a, t, j+1, num+1);
        t.pop_back();
    }
}

int main(){
    cin>>n>>m;
    int a[n];
    for(int i=0;i<n;i++)
        cin>>a[i];
    vector<int> t;
    F(a, t, 0, 0);
    cout<<Min<<endl;
    return 0;
}

from itertools import combinations
dims = list(map(int, input().split()))
if len(dims) == 2:
    n = dims[0]
    k = dims[1]
else:
    n = dims[0]
    k = int(input())

nums = list(map(int, input().split()))
 
mini_res = float('inf')
takes = combinations(nums, k)

def get_rest(nums, take):
    for t in take:
        if t in nums:
            nums.remove(t)
    return nums

for take in takes:
    take = list(take)
    rest = get_rest(nums[:], take)
    bias = 0
    for t in take:
        for r in rest:
            bias += abs(t-r)
    mini_res = min(bias, mini_res)
print(mini_res)

import sys
line=sys.stdin.readline().strip().split()
n=int(line[0])
k=int(line[1])
line=sys.stdin.readline().strip().split()
data=[]
for l in line:
    data.append(int(l))
take=[]
out=[]
def f(take, rest):
    if len(take)==k:
        summ=0
        for t in take:
            for r in rest:
                summ+=abs(t-r)
                if len(out)>0 and summ>=min(out):
                    return
        out.append(summ)
        return
    for i in range(len(rest)):
        f(take+[rest[i]], rest[0:i]+rest[i+1:])
f(take,data)
print(min(out)) 

****详细过程点击这里*****
牛客官网给的提示是 动态规划和穷举，我没有想出动态规划的方案，这里用穷举的方式可以通过。

对于给定的N个数，小爱同学拿了其中的K个数，那么也就是从N个数中取出K个数，共有种情况。遍历这种情况，得到最小的即为最后的答案。

那么问题就转化成了求N个数中取K个数的所有组合情况，本题用combination(data, r)函数，data为list类型数据，r表示从data中取出r个数。combination函数能够返回所有的r个数的组合。关于组合函数combination(data, r)的详解可以看文章列表排列组合（撰写中...）
****详细过程点击这里*****

import java.util.Scanner;



/*
 * @author Moze 2020
 * 此题目题量较小，使用穷举法可以求解。
 * 递归出共有2的N次方种情况，可以进行一些剪枝
 * 我只减去了最后小爱个数不等于k的就可以了
 * 注：个人感觉此题不能够用动态规划吧。
 * 原因：设index为止，小爱分了i个数，和index时刻小爱分了i个数还是i-1个数 并不能直接联系，必须等到最后时刻才能够确定
 */
public class Main {
	static int N;
	static int a[];
	static int k;
	static int min=Integer.MAX_VALUE;
	public static void main(String[] args) {
		Scanner aa= new Scanner(System.in);
		N = aa.nextInt();
		k = aa.nextInt();
		a=new int[N];
		for(int i=0;i<N;i++){
			a[i]=aa.nextInt();
		}
		m(0,new int[N],new int[N],0,0);
		System.out.println(min);
		
	}
	public static void m(int index,int[] xi,int[] ai,int num_xi,int num_ai){
		if(index == N){
			if(num_ai != k){
				return ;
			}
			int sum=0;
			for(int i=0;i<num_ai;i++){
				for(int j=0;j<num_xi;j++){
					sum+=Math.abs(ai[i]-xi[j]);
				}
			}
			min = Math.min(min, sum); 
			return ;
		}
		if(num_ai<k){
			ai[num_ai]=a[index];
			m(index+1,xi,ai,num_xi,num_ai+1);
		}
		xi[num_xi]=a[index];
		m(index+1,xi,ai,num_xi+1,num_ai);
	}
	
	
	
}

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int cal_F(vector<int> l_1, vector<int> l_2)
{
    int res=0;
    for(int i=0; i<l_1.size(); i++)
        for(int j=0; j<l_2.size(); j++)
        {
            res+=abs(l_1[i]-l_2[j]);
        }
    
    return res;
}
    
void recur(int k, int i, int level, vector<int> nums, vector<int> l_1, vector<int> l_2,
          int &min_f)
{
    if(level==k)
    {
         for(int temp_i=i; temp_i<nums.size(); temp_i++)
             l_2.push_back(nums[temp_i]);
        int f=cal_F(l_1, l_2);
        min_f=min(f, min_f);
    }
    else{
       for(int begin=i; begin<nums.size()-k+level+1; begin++)
       {
         vector<int> temp_l1=l_1;
         vector<int> temp_l2=l_2;
        
         temp_l1.push_back(nums[begin]);
         for(int temp_i=i; temp_i<begin; temp_i++)
             temp_l2.push_back(nums[temp_i]);
        
         recur(k, begin+1, level+1, nums, temp_l1, temp_l2, min_f);
       }
    }
}
    
int main()
{
    int N,K;
    cin>>N>>K;
    vector<int> nums(N,0);
    for(int i=0; i<N; i++)
        cin>>nums[i];
    
    int min_F=0x3f3f3f3f;
    vector<int> l1;
    vector<int> l2;
    recur(K, 0, 0, nums, l1,l2,min_F);
    cout<<min_F<<endl;
    return 0;
}

/*
   利用回溯法找出小爱可能的所有组合放在一个二维数组中 res
   原本的总的输入数组 依次减去 得到二维数组每一行 就可以得到小溪的所有可能 tem
   用给的公式计算得分
*/
#include<bits/stdc++.h>
using namespace std;

void Core(vector<int> vec, vector<vector<int>>& res, vector<int> tem, int i, int num)
{
    if(num == 0) 
    {
        res.push_back(tem);
        return;
    }
    for(int j = i;j < vec.size();j++)
    {
        tem.push_back(vec[j]);
        Core(vec, res, tem, j +1, num-1);
        tem.pop_back();
    }
}
int main()
{
    int n,m;cin >> n >>m ;
    vector<int> vec(n,0);
    for(int i = 0; i < n;i++) cin >> vec[i];
    vector<vector<int>> res;
    vector<int> tem;
    Core(vec, res,tem, 0,m);
    int mi = INT_MAX;
    
    
    for(int i = 0; i < res.size();i++)
    {
        vector<int> tem;
        set<int> ss;  //将每一个行放在一个临时的set中
        for(int j = 0; j < m;j++) ss.insert(res[i][j]);
        //总的可能减去小爱的可能得到小溪的可能
        for(int j = 0; j < n;j++)
        {
            if(ss.find(vec[j]) != ss.end()) ss.erase(vec[j]);
            else tem.push_back(vec[j]);
        }
        int k = 0;
        for(int x = 0; x < res[0].size();x++)
        {
            for(int y = 0; y < tem.size();y++)
            {
                k += abs(res[i][x] - tem[y]);
            }
        }
        mi = min(mi, k);
    }
    cout << mi << endl;
    return 0;
}