题解 | #数组分组#

数组分组

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")

全部评论

相关推荐

叶扰云倾:进度更新,现在阿里云面完3面了,感觉3面答得还行,基本都答上了,自己熟悉的地方也说的比较细致,但感觉面试官有点心不在焉不知道是不是不想要我了,求阿里收留,我直接秒到岗当阿里孝子,学校那边的房子都退租了,下学期都不回学校,全职猛猛实习半年。这种条件还不诱人吗难道 然后现在约到了字节的一面和淘天的复活赛,外加猿辅导。华为笔试完没动静。 美团那边之前投了个base广州的,把我流程卡麻了,应该是不怎么招人,我直接简历挂了,现在进了一个正常的后端流程,还在筛选,不知道还有没有hc。
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-10 15:58
投个小米提前批试试水,先投一个岗位看看形势,不行就再沉淀一下投第二个岗位,莫辜负
Java抽象带篮子:我嘞个骚刚,已经开始研发6g了吗
投递小米集团等公司7个岗位
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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