YACS|2023年2月月赛|丙组 平分数字（一）

平分数字（一）

题目描述

给定 n 个整数：a1,a2,⋯ ,an​，请判定能否将它们分成两个部分（不得丢弃任何数字），每部分的数字之和一样大。

输入格式

第一行：单个整数 n；

第二行：n 个整数，表示 a1,a2,⋯ ,an。

输出格式

若能否平分，输出 Matched，否则输出 No

数据范围

对于 50%的数据，1≤n≤18；

对于 100% 的数据，1≤n≤24；

−10,000,000≤ai≤10,000,000。

样例数据

输入:

4

1 2 3 4

输出:

Matched

说明:

1 + 4 = 2 + 3

输入:

3

2 2 2

输出:

No

题解

写了两个dfs函数，分别对应两种不同dfs实现方式。

注意：题目数据含负数，所以不能用剪枝。

#include <bits/stdc++.h> 
using namespace std;  

int n;
long long a[25];
long long sum=0, avg;
//第m个数，数组b当前下标 
bool dfs(int m, long long sumb, long long sumc){
//    if(m>n){
//        return false;
//    }
    //剪枝
    if(sumb+a[m]==avg || sumc+a[m]==avg){
        return true;
    }
    
    bool flag=false;
    //a[m]放入b组
    //if(sumb+a[m] < avg){ //数据 包含负数，不能优化 
        flag = dfs(m+1, sumb+a[m], sumc);
    //}
    
    //a[m]放入c组 
    if(flag==true){
        return true;
    }
    //if(sumc+a[m] < avg){//数据 包含负数，不能优化 
        return dfs(m+1, sumb, sumc+a[m]);
    //}
    //else{
        return false;
    //}
}

bool res=false;
void dfs2(int m, long long sumb, long long sumc){
    if(m>n){
        if(sumb==sumc) res = true;
        return;
    }
    //数据 包含负数，不能剪枝 
    /*if(sumb+a[m]<=avg)*/ dfs2(m+1, sumb+a[m], sumc);
    /*if(sumc+a[m]<=avg)*/ dfs2(m+1, sumb, sumc+a[m]);
    return;
}

int main()
{    
    cin>>n;
    for(int i=1; i<=n; i++){
        cin>>a[i];
        sum+=a[i];
    }
    if(sum%2){ //余数可能是负数，不能写成 sum%2==1或 sum%2>0 
        cout<<"No";
        return 0;
    }
    avg = sum/2;

/*//方法一： 
    if(dfs(1,0,0)) cout<<"Matched";
    else cout<<"No";
*/

//方法二： 
    dfs2(1,0,0);
    if(res == true) cout<<"Matched";
    else cout<<"No";
    getchar();
    getchar();
    system("pause");
    return 0;
}