华为机试HJ93:数组分组

简介: 华为机试HJ93:数组分组

题目描述:

输入int型数组,询问该数组能否分成两组,使得两组中各元素加起来的和相等,并且,所有5的倍数必须在其中一个组中,所有3的倍数在另一个组中(不包括5的倍数),能满足以上条件,输出true;不满足时输出false。

本题含有多组样例输入。

输入描述:

第一行是数据个数,第二行是输入的数据

输出描述:

返回true或者false

示例:

输入:

4

1 5 -5 1

3

3 5 8


输出:

true

false


说明:

第一个样例:

第一组:5 -5 1

第二组:1

第二个样例:由于3和5不能放在同一组,所以不存在一种分法。


解题思路:

这题可以用递归解决。首先输入n个数字,将5的倍数和3的倍数分别累加得到sum3和sum5,其他的数字放在容器v中;用add函数进行递归,单个数字从容器中提出来加到sum3或者sum5中,以此类推,直到所有数字都加进去了;之后,判断sum3和sum5是否一致,然后一级级返回标识符即可。

测试代码:

#include <iostream>
#include <string>
#include <vector>
using namespace std;
bool add(int sum5,int sum3,vector<int> v)
{
    if(v.size()==0)
    {
        if(sum5==sum3)
            return true;
        else
            return false;
    }
    else{
        int b=v.back();
        v.pop_back();
        return add(sum5+b,sum3,v)||add(sum5,sum3+b,v);
    }
}
int main()
{
    int num;
    while(cin>>num)
    {
        int sum3=0;
        int sum5=0;
        vector<int> v;
        for(int i=0;i<num;++i)
        {
            int temp;
            cin>>temp;
            if(temp%5==0)
                sum5+=temp;
            else if(temp%3==0)
                sum3+=temp;
            else
                v.push_back(temp);
        }
        if(add(sum5,sum3,v))
            cout<<"true"<<endl;
        else
            cout<<"false"<<endl;
    }
    return 0;
}
相关文章
|
算法
华为机试HJ14:字符串排序
华为机试HJ14:字符串排序
|
人工智能
华为机试HJ26:字符串排序
华为机试HJ26:字符串排序
|
容器
华为机试HJ80:整型数组合并
华为机试HJ80:整型数组合并
226 1
|
容器
华为机试HJ102:字符统计
华为机试HJ102:字符统计
163 1
华为机试HJ96:表示数字
华为机试HJ96:表示数字
109 1
华为机试HJ106:字符逆序
华为机试HJ106:字符逆序
119 1
|
Serverless
华为机试HJ30:字符串合并处理
华为机试HJ30:字符串合并处理
华为机试HJ84:统计大写字母个数
华为机试HJ84:统计大写字母个数
|
容器
华为机试HJ10:字符个数统计
华为机试HJ10:字符个数统计
|
容器
华为机试HJ94:记票统计
华为机试HJ94:记票统计