将一个数组拆分成两个数组，两个数组的差的绝对值最小

末蓝、 2022-09-27 00:27 170阅读 0赞

要求如题，是qq群里一个大神让我敲的demo，花了2个小时，用c语言实现。但是数组的元素只能是正数！

思路是:  
1).先求出数组的总和sum, sum/2=mid  
2).然后将数组的元素跟mid比较，取出跟mid最接近的元素，放在第一个小数组里，然后在原来数组删除刚刚被取出的元素，更新原来数组  
3).接着再取出离mid最近的元素，放在第二个小数组，在原数组中删除刚刚被取出的元素，更新原来数组  
4).遍历原来数组，重复2和3，往后的元素放在第一个小数组或者第二个小数组，取决于两个小数组的所有元素的总和，哪个总和小就放在哪个小数组

#include<stdio.h>
    void binaryMiun(int s[], int n);
    int abs(int a);
    int main() {
        int n, i, t;
        int s[n];
        printf("输入原始数组的个数: \n");
        scanf("%d", &n);
        printf("请输入数组元素：\n");
        for(i = 0; i < n; i++) {
            scanf("%d", &t);
            s[i] = t;
        } 
        printf("您输入的数组是:");
        for(i = 0; i < n; i++) {
            printf("%d ", s[i]);
        }
        printf("\n");
        binaryMiun(s, n);
        return 0;
    }
    void binaryMiun(int s[], int n) {
        int i, h, mid, temp, k;
        int l[n];//第一个小数组
        int r[n];//第二个小数组
        int min;
        int lcount = 0;
        int rcount = 0;
        int sum = 0;
        int suml = 0;//第一个小数组元素总和
        int sumr = 0;//第二个小数组元素的总和
        int j = 0;
        //该for循环遍历数组求元素的总和sum
        for(int i = 0; i < n; i++) {
            sum += s[i];
        }
        //mid 为元素总和的一半
        mid = sum/2;
        for(h = 0; h < n;) {
            min = mid - s[0];
            //找出离mid最近的元素
            for(i = 0; i < n; i++) {
                temp = mid - s[i];
                if(temp <= min) {
                    min = temp;
                    //距离mid最近的元素的下标
                    j = i;
                }
            }
            printf("出列的元素是------>%d\n", s[j]);
            //将取出的元素放在元素总和较小的数组
            if(suml <= sumr) {
                l[lcount++] = s[j];
                suml += s[j];
            }
            else {
                r[rcount++] = s[j];
                sumr += s[j];
            }
            //将刚刚在原数组取出的元素删除，更新原数组
            for(k = j; k < n; k++) {
                s[k] = s[k+1];
            }
            n--;
            printf("原数组变为:");
            for(k = 0; k < n; k++) {
                printf("%d ", s[k]);
            }
            printf("\n");
        }
        printf("第一个数组：");
        for(i = 0; i < lcount; i++) {
            printf("%d ", l[i]);
        }
        printf("\n第二个数组：");
        for(i = 0; i < rcount; i++) {
            printf("%ld ", r[i]);
        }
        printf("\n拆分成两个数组的最小绝对值之差是：%d\n", abs(sumr-suml));
    }
    int abs(int a) {
        if(a < 0) 
            return -a;
        else
            return a;
    }

测试：

![这里写图片描述][SouthEast]

[SouthEast]: /images/20220708/df3176c7d87b473a9cbbb83362d577bf.png