小爱和小溪有N个数字,他们两个想公平的分配这些数字。小爱拿的数字集合为I=「i1, i2, ik」,小溪获得剩下的J,J=「j1, j2, jn-k」。但是他们衡量分配公平与否的原则与众不同:
在小爱拿到其中的K个数字的前提下,计算出他们分配偏差f(I)的最小值。
小爱和小溪有N个数字,他们两个想公平的分配这些数字。小爱拿的数字集合为I=「i1, i2, ik」,小溪获得剩下的J,J=「j1, j2, jn-k」。但是他们衡量分配公平与否的原则与众不同:
在小爱拿到其中的K个数字的前提下,计算出他们分配偏差f(I)的最小值。
输入第一行两个数字,分别表示总的数字量N和小爱拿的数字量K。第二行有N个数字,表示每个数字的值。
输出一个数字,表示分配偏差f(I)的最小值。
4 1 3 3 3 1
2
#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; }
import java.io.*; public class Main{ static int[] nums;//存放总的数字 static int[] ai;//小爱取的数 static boolean[] isSelect;//总的数字中被小爱取的数为true static int min=Integer.MAX_VALUE;//最小偏差 public static void main(String[] args) throws IOException{ BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); String[] line1=br.readLine().split(" "); int n=Integer.parseInt(line1[0]); int k=Integer.parseInt(line1[1]); if(k==0 || k>n){ System.out.println(0); return; } nums=new int[n]; isSelect=new boolean[n]; ai=new int[k]; String[] line2=br.readLine().split(" "); for(int i=0;i<n;i++){ nums[i]=Integer.parseInt(line2[i]); } backtracking(n,k); System.out.println(min); } /* 回溯算法,从后往前 */ static void backtracking(int n,int k){ if(k==0){//递归的终止条件 int sum=0; for(int i=0;i<ai.length;i++){ for(int j=0;j<nums.length;j++){ if(!isSelect[j]){ sum+=Math.abs(ai[i]-nums[j]); } } } min=Math.min(min,sum); return; } //这里从n-1开始取,如果i<k-1,那么就算你把前面的都取完也取不到k个数 //其实也就是鸽笼原理 for(int i=n-1;i>=k-1;i--){ ai[k-1]=nums[i]; isSelect[i]=true; backtracking(i,k-1); isSelect[i]=false; } } }
/* 利用回溯法找出小爱可能的所有组合放在一个二维数组中 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; }