首页 > 试题广场 >

公平划分

[编程题]公平划分
  • 热度指数:1759 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解

小爱和小溪有N个数字,他们两个想公平的分配这些数字。小爱拿的数字集合为I=「i1, i2, ik」,小溪获得剩下的J,J=「j1, j2, jn-k」。但是他们衡量分配公平与否的原则与众不同:

在小爱拿到其中的K个数字的前提下,计算出他们分配偏差f(I)的最小值


输入描述:
输入第一行两个数字,分别表示总的数字量N和小爱拿的数字量K。第二行有N个数字,表示每个数字的值。


输出描述:
输出一个数字,表示分配偏差f(I)的最小值。
示例1

输入

4 1
3 3 3 1

输出

2
具体解题思路可见博客及代码:https://blog.csdn.net/qq_40880600/article/details/99345244
发表于 2019-08-12 22:06:45 回复(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;
}

发表于 2019-12-16 00:44:32 回复(0)

我的思路是,先从小到大排列 ,取最中间的数是肯定满足要求的,依次取,最后分成两组,不知道为什么AC只有百分之40

#include<bits/stdc++.h>
using namespace std;
int main(){
int n,m,k;
    cin>>n>>m;
    vector<int> q,w;
    for(int i=0;i<n;i++){
        cin>>k;
        q.push_back(k);
    }
    sort(q.begin(),q.end());
    int len=min(m,n-m);
    int sum=0;
    for(int i=0;i<len;i++){
        vector<int> q1(q);
        vector<int> q2(q);
        int sum1=0,sum2=0;
        for(int j=0;j<q.size();j++){
           sum1+=abs(q[q.size()/2]-q[j]);
           sum2+=abs(q[q.size()/2-1]-q[j]);
        }
      if(sum1<=sum2){
          q.erase(q.begin()+q.size()/2);
          w.push_back(q[q.size()/2]);
      }
        else{
           q.erase(q.begin()+q.size()/2-1);
            w.push_back(q[q.size()/2-1]);
        }
    }
    for(int i=0;i<w.size();i++){
        for(int j=0;j<q.size();j++){
            sum+=abs(w[i]-q[j]);
        }
        
    }
cout<<sum;     
    }




发表于 2020-08-17 15:26:09 回复(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)

发表于 2020-08-13 15:22:20 回复(0)
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)) 
运行超时:您的程序未能在规定时间内运行结束,请检查是否循环有错或算法复杂度过大。点击对比用例标准输出与你的输出
case通过率为60.00%
好痛苦。。。
编辑于 2020-07-24 22:31:05 回复(0)

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

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

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

发表于 2020-07-12 21:27:25 回复(0)
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);
	}
	
	
	
}



发表于 2020-06-26 20:41:18 回复(0)
#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;
}

发表于 2020-06-25 18:14:34 回复(0)
import java.util.*;
public class Main {
    public static void main(String[] args) {
       Scanner sc =new Scanner(System.in);
        int N=sc.nextInt(),count_ai=sc.nextInt();
        int [] arr =new int[N];
        for (int i = 0; i < arr.length; i++) {
            arr[i]=sc.nextInt();
        }
        List<Integer> list =new ArrayList<Integer>();
        int[] ai=new int[count_ai];
        list = DistributionMin_Recursive(arr,count_ai,ai,list);
        int min=list.get(0);
        for (int i = 1; i < list.size(); i++) {
            if(list.get(i)<min)min=list.get(i);
        }
        System.out.println(min);
    }
    private static List<Integer> DistributionMin_Recursive(int[] arr, int count_ai, int[] ai, List<Integer> list) {
        if(count_ai==0){
            int sum=0; 
            for (int i = 0; i < ai.length; i++) {
                for (int j = 0; j < arr.length; j++) {
                    if(arr[j]!=-1){ sum+=Math.abs(ai[i]-arr[j]); }
                }
            }
            list.add(sum);
        }else{
            for (int i = 0; i < arr.length; i++) {
                if(arr[i]==-1){ continue; }
                else { 
                    ai[count_ai-1]=arr[i]; 
                    arr[i]=-1;
                    list =DistributionMin_Recursive(arr,count_ai-1,ai,list);
                    arr[i]=ai[count_ai-1];
                }
            }
        }
        return list;
    }

运行结果:
您的代码已保存
运行超时:您的程序未能在规定时间内运行结束,请检查是否循环有错或算法复杂度过大。
case通过率为80.00%

大家瞅瞅这可咋整
发表于 2019-08-26 12:03:03 回复(0)
这道题归在了dp,以为要用到中位数的性质,中位数和其他数的绝对差最小,但是后面取数会影响前面取数的结果,不满足动态规划的无后效性,也就行不通了。
还是感谢大佬们的思路,用的是回溯,不知道为什么总说数组访问越界,只过了80%,
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;
        }
    }
}


编辑于 2019-08-24 19:43:39 回复(0)
c++抄的回溯法
/*
   利用回溯法找出小爱可能的所有组合放在一个二维数组中 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;
}

发表于 2019-08-04 22:40:52 回复(3)
怎么没有人做,想很久做不出来。
发表于 2019-08-02 18:06:23 回复(1)