题解 | #数组分组#

数组分组

https://www.nowcoder.com/practice/9af744a3517440508dbeb297020aca86

其实直觉来看应该是很标准的DFS,每个数字只有两种可能,放在A数组和放在B数组,重要的是要记得恢复原本数组状态。

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

int suma = 0; //记录数组A的和
int sumb = 0; //记录数组B的和
int cnt = 0;
int c[55];


bool dfs(int i){
    // cout << i << " " << suma << " " << sumb << endl;
    if (i == cnt){
        if (suma == sumb) return true;
        return false;
    }
    // i 放在A中
    suma += c[i];
    if (dfs(i+1)) return true;
    suma -= c[i];

    // i 放在B中
    sumb += c[i];
    if (dfs(i+1)) return true;
    sumb -= c[i];
    return false;
}


int main() {
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++){
        int a; cin >> a;
        if (a % 5 == 0) suma += a;
        else if (a % 3 == 0) sumb += a;
        else{
            c[cnt++] = a;
        }
    }
    if (dfs(0)) cout << "true";
    else cout << "false";
    return 0;
}
// 64 位输出请用 printf("%lld")

全部评论

相关推荐

牛客92804383...:在他心里你已经是他的员工了
点赞 评论 收藏
分享
风中翠竹:真的真的真的没有kpi。。。面试官是没有任何kpi的,捞是真的想试试看这个行不行,碰碰运气,或者是面试官比较闲现在,没事捞个人看看。kpi算HR那边,但是只有你入职了,kpi才作数,面试是没有的。
双非有机会进大厂吗
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务