首页 > 试题广场 > 公平划分
[编程题]公平划分
  • 热度指数:562 时间限制: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)
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)

问题信息

上传者:小小
难度:
5条回答 1423浏览

热门推荐

通过挑战的用户

查看代码