题解 | #牛牛的数组匹配#

#include <stdio.h>
#include <math.h>

int* compute(int arr2[], int m, int i, int sum1, int sum2){
    int arr[2], sub = 0;; //存放两个参数 找到本轮最优解时候的sum 和 j     
    for(int n = 0; n < i; n++)
            sum2 -= arr2[n]; //本轮初始值
    for(int j = m - 1; j >= i; j--){
        if(abs(sum2 - arr2[j] - sum1) < abs(sum2 - sum1)) //比较差值
            sum2 -= arr2[j];
        else{
            arr[0] = sum2; //当轮最优解元素和
            arr[1] = j;    //当轮最优解尾元素下标
            break;
        } 
    }
    return arr;
}
/*思路：从完整数组开始，不断去掉前面的一个元素，用剩下的子数组进行下轮比较;
*每轮判断规则(如果满足减去数组2当前的最后一个元素后，如果和数组1差值变小了，
*就继续减去尾元素，直到满足差值最小,得到本轮最优解; 用该值和下一轮进行比较，
*如果下一轮差值更小，则继续切割数组，找更下一轮，直到不满足，然后根据i，j位置输出数组元素;  
*/
int main(){
    int n, m, res, arr1[10], arr2[10], sum1 = 0, sum2 = 0;
    scanf("%d %d", &n, &m);
    for(int i = 0; i < n; i++){
        scanf("%d", &arr1[i]);
        sum1 += arr1[i];
    }
    for(int j = 0; j < m; j++){
        scanf("%d", &arr2[j]);
        sum2 += arr2[j];
    }
    int min = *(compute(arr2, m, 0, sum1, sum2));
    for(int i = 1; i < m; i++){
        res = *compute(arr2, m, i, sum1, sum2);
        if(abs(res - sum1) < abs(min - sum1)) //比较差值
			min = res;	
        else{
        	i--; //不满足要回溯 
            int j = *(compute(arr2, m, i, sum1, sum2) + 1);
            for(int s = i; s <= j; s++)
                printf("%d ", arr2[s]);
            break;
        }
    }
    return 0;
}