首页 > 试题广场 > 公平划分
[编程题]公平划分

小爱和小溪有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)
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)