首页 > 试题广场 >

数组分组

[编程题]数组分组
  • 热度指数：113289 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
输入int型数组，询问该数组能否分成两组，使得两组中各元素加起来的和相等，并且，所有5的倍数必须在其中一个组中，所有3的倍数在另一个组中（不包括5的倍数），不是5的倍数也不是3的倍数能放在任意一组，可以将数组分为空数组，能满足以上条件，输出true；不满足时输出false。

数据范围：每个数组大小满足 ，输入的数据大小满足

输入描述:
第一行是数据个数，第二行是输入的数据


输出描述:
返回true或者false
示例1

输入

4
1 5 -5 1

输出

true

说明

第一组：5 -5 1
第二组：1
示例2

输入

3
3 5 8

输出

false

说明

由于3和5不能放在同一组，所以不存在一种分法。
算法知识视频讲解
添加回答
Python
牛客980779794号头像 牛客980779794号 
def iscouple(s,left,right):
    #递归终点
    if len(s)==0:
        if sum(left)==sum(right):
            return True
        else:return False
    #数字放在左组或者右组
    for i in range(len(s)):
        news = s[:i]+s[i+1:]
        if iscouple(news,left,right+[s[i]]) or iscouple(news,left+[s[i]],right):
            return True
    return False
while True:
    try:
        n = int(input())
        s = [int(x) for x in input().strip().split()]
    except:
        break
    #初步判断所有数字是否能分成两组,总和不被2整除就不能
    if sum(s)%2!=0:
        print('false')
        continue
    #根据题目要求先将5的倍数放在右组,剩余的数里再将3的倍数放在左组,剩下的放nums里
    left=[]
    right=[]
    nums=[]
    for i in s:
        if i%5==0:
            right+=[i]
        elif i%3==0:
            left+=[i]
        else:
            nums+=[i]
    if iscouple(nums,left,right):
        print('true')
    else: print('false')

编辑于 2021-06-24 10:30:20 回复(0)
Python
星凌九天头像 星凌九天
while True:
    try:
        num=int(input())
        list1=list(map(int,input().split()))
        s5=0
        s3=0
        s1=0
        list2=[0]
        list3=[]
        n=0
        for i in list1:
            if i%5==0:
                s5+=i
            elif i%3==0:
                s3+=i
            else:
                n+=1
                for j in list2:
                    list3.append(j+i)
                    list3.append(j-i)
                list2=list3
                list3=[]
        if abs(s5-s3) in list2:
            print('true')
        else:
            print('false')
    except:
        break
发表于 2021-03-18 14:00:12 回复(1)
Python
Offer招手了吗头像 Offer招手了吗 
"""
只需要一个数字now_sum存储假设存在的两数组总和的差。分组可以假定一数组均加和到now_sum, 二数组均取相反值加和到now_sum。
这样，两数组加和相等的条件就变成了：所有数字加和到now_sum后now_sum=0.
常数级额外空间
"""

def get_res(now_sum, plus, i):
    now_sum += plus * nums[i]    # 只需要一个now_sum记录总和。一数组的加，二数组的减。plus控制加减
    if len(nums) == i+1:    # 到头了返回总和是否为0（两数组加和相等）
        return now_sum == 0
    if nums[i+1] % 5 == 0:    # 5 的倍数必去1数组
        return get_res(now_sum, 1, i+1)
    elif nums[i+1] % 3 == 0:    # 3的倍数必去2数组
        return get_res(now_sum, -1, i+1)
    return get_res(now_sum, 1, i+1) or get_res(now_sum, -1, i+1)    # 深搜

while True:
    try:
        a = int(input())
        nums = list(map(int, input().split()))
        print("true" if get_res(0, 1, 0) or get_res(0, -1, 0) else "false") # 建议牛客优化嗷。太蠢了
    except Exception as err:
        break
其实是一道二叉树根到叶节点路径总和的变种题。深搜解决
编辑于 2021-02-24 11:33:18 回复(0)
Python
CYRIL_MENG头像 CYRIL_MENG 
def is_group(l3,l5,l,i=-1):
    if i==len(l) and sum(l3)==sum(l5): 
        return True
    elif i==len(l) and sum(l3)!=sum(l5): 
        return False
    else:
#         print(l3,l5)
        i+=1
        return is_group(l3,l5+l[i:i+1],l,i)&nbs***bsp;is_group(l3+l[i:i+1],l5,l,i)
while True:
    try:
        n = int(input())
        nums = list(map(int,input().split()))
        l3 = []
        l5 = []
        l = []
        for i in nums:
            if i%3 == 0:
                l3.append(i)
            elif i%5 == 0:
                l5.append(i)
            else:
                l.append(i)
        if is_group(l3, l5, l):
            print('true')
        else:
            print('false')
    except:
        break

发表于 2021-02-22 21:28:01 回复(0)
Python
牛客627860403号头像 牛客627860403号 
def do(a):
    b = map(int, raw_input().strip().split())
    m3, m5, pos, neg = [], [], [], []
    
    for _ in b:
        if _%5 == 0:
            m5.append(_)
        elif _%3 == 0:
            m3.append(_)
        elif _ > 0:
            pos.append(_)
        else:
            neg.append(_)
    tar = abs(sum(m3)-sum(m5)) # target gap
    cur = sum(pos) - sum(neg) # available max gap
    if tar > cur&nbs***bsp;(cur - tar)%2:
        print 'false'
        return
    tgt = (cur - tar) / 2 # move number will make 2 fold change
    r = [0] * (tgt+1)
    r[0] = 1
    for n in pos+neg:
        n = abs(n)
        for v in range(n, tgt+1):
            r[v] += r[v-n]
    if r[tgt]:
        print 'true'
    
while 1:
    try:
        do(raw_input().strip())
    except Exception as e:
        import traceback
        traceback.print_exc()
        break


编辑于 2021-01-09 21:23:34 回复(0)
Python
bancaolanmu头像 bancaolanmu
提交会出错20%，但是专门调试和自测都是对的，很疑惑

import itertools
total = 0

while True:
    try:
        t=int(input())
        l = list(map(int,input().split()))
        if sum(l)%2 ==0:
            s5=[]
            s3=[]
            sr=[]
            aver = sum(l)/2
            for v in l:
                if v%5==0:
                    s5.append(v)
                elif v%3 ==0:
                    s3.append(v)
                else:
                    sr.append(v)
            if len(sr) ==0:
                if sum(s5) == aver or sum(s3) == aver:
                    total+=1
            else:
                for i in range(0,len(sr)+1):
                    for subset in set(itertools.combinations(sr, i)):
                        if sum(s5) + sum(subset) == aver or sum(s3) + sum(subset) == aver:
                            total +=1
    except:break

if total == 0:
     print('false')
else:
     print('true')

发表于 2020-12-23 04:14:18 回复(0)
Python
大溪地渔民头像 大溪地渔民 
def helper(sum3, sum5, count):
    if count==len(others):
        if sum3==sum5:
            return True
        return False
    return helper(sum3+others[count], sum5, count+1)&nbs***bsp;helper(sum3, sum5+others[count], count+1)


while True:
    try:
        n, nums = int(input()), list(map(int, input().split()))
        sum15, sum3, sum5, others = 0, 0, 0, []
        for i in nums:
            if i%15 == 0:
                sum15 += i
            elif i%3 == 0:
                sum3 += i
            elif i%5 == 0:
                sum5 += i
            else:
                others.append(i)
        if sum15:
            print("false")
            continue
        print("true" if helper(sum3, sum5, 0) else "false")
    except:
        break

发表于 2020-12-18 22:35:31 回复(0)
Python
张浩头像 张浩
1：sum5 - sum3 = y - x 
2：other       = x + y 
两个公式相加：sum5 - sum3 + other = 2*y
while True:
    try:
        a=int(input())
        b=list(map(int, input().split()))
        s3=[]
        s5=[]
        s=[]
        for i in b:
            if i%3==0:
                s3.append(i)
            elif i%5==0:
                s5.append(i)
            else :
                s.append(i)
        sum3=sum(s3)
        sum5=sum(s5)
        othersum=sum(s)
        y=(othersum-sum3+sum5)/2
        def search(list1,num):
            if num==0:
                return 1
            elif list1==[]:
                return 0
            else:
                return search(list1[1:], num) or search(list1[1:], num-list1[0])
        if y%1!=0:
            print('false')
        elif search(s,y):
            print('true')
        else:
            print('false')
    except:
        break
发表于 2020-11-17 13:04:13 回复(0)
Python
软弱的我头像 软弱的我
可以把遍历列表的子列表 
from itertools import combinations
while True:
    try:
        n = int(input())
        ls = list(map(int, input().split()))
        ls1, ls2, ls3 = [], [], []

        for i in ls:
            if i % 5 == 0:
                ls1.append(i)
            elif i % 3 == 0:
                ls2.append(i)
            else:
                ls3.append(i)
        x = sum(ls)/2 - sum(ls1)
        judge = False
        for i in range(len(ls3)+1):
            ja = 0
            result = set(combinations(ls3,i))
            for j in result:
                if sum(j) == x:
                    judge = True
                    ja = 1
                    break
            if ja == 1:
                 break
        if judge == True:
            print('true')
        else:
            print('false')
    except:
        break

发表于 2020-11-14 13:23:53 回复(0)
Python
whynotyeaaah头像 whynotyeaaah
python版解法，思路与已有的差不多，只是我的代码中增加了剪枝，效率应该更高一些。剪枝的前提是把剩下的元素先排序，这个复杂度O(nlogn)相较于递归的O(2n)可以忽略不计。 
def addup2n(arr, n):     
    if n == 0:
        return True
    if not arr:
        return False
    if arr[0] > 0 and (n < arr[0]&nbs***bsp;n > sum(arr)):
        return False
    if arr[-1] < 0 and (n > arr[-1]&nbs***bsp;n < sum(arr)):
        return False
    if addup2n(arr[1:], n-arr[0])&nbs***bsp;\
            addup2n(arr[1:], n):
        return True
    return False

def find(arr, n):
    if not arr:
        return True if n==0 else False
    sam = sum(arr)
    if sam % 2 != n % 2:
        return False
    gsum = (sam-n) // 2
    return addup2n(sorted(arr), gsum)

while True:
    try:
        n = int(input())
        arr = list(map(int, input().split()))
        five, thr, rem = [], [], []
        for i in arr:
            if i % 5 == 0:
                five.append(i)
            elif i % 3 == 0:
                thr.append(i)
            else:
                rem.append(i)
        dif = abs(sum(five) - sum(thr))
        res = find(rem, dif)
        print('true' if res else 'false')
    except:
        break

编辑于 2020-10-27 20:44:47 回复(0)
Python
苏客头像 苏客
牛客网的判卷系统真的有病，本地可以执行，自测可以执行。但是就是print('true')输出不了，在print('true')语句前后加上print('123')都可以输出，就是这句话输出不了，这道题真是日了牛客网了 
def findm(n, m):
    if m < 1&nbs***bsp;len(n) < 1:
        return
    elif m in n:
        return True
    if findm(n[:-1], m):
        return True
    elif findm(n[:-1], m - n[-1]):
        return True
    else:
        return False
def pf(f):
    if f:
        print('true')
    else:
        print('false')
try:
    n = int(input())
    m = list(map(int, input().split()))
    li3 = []
    li5 = []
    res = []
    for i in range(len(m)):
        if m[i] % 5 == 0:
            li5.append(m[i])
        elif m[i] % 3 == 0:
            li3.append(m[i])
        else:
            res.append(m[i])
    sumall = sum(m)
    if sumall % 2:
        print('false')
    else:
        M = int(sumall / 2 - sum(li5))
        pf(findm(res,M))
        #if findm(res, M):
except Exception as e:
    print(e)
发表于 2020-09-03 17:07:20 回复(1)
Python
工作已找到头像 工作已找到
真的搞了好久。。。。。。。。。
while True:
    try:
        def search(resList,subSum):
            if subSum == 0:
                res.append(1)
            else:
                for j in range(len(resList)):
                    search(resList[j + 1:], subSum - resList[j])
        n = int(input())
        nums = list(map(int,input().split()))
        five = []
        three = []
        totalSum = 0
        fiveSum = 0
        threeSum = 0
        for i in range(n):
            totalSum = totalSum + nums[i]
            if nums[i]%5 == 0:
                five = five + [nums[i]]
                fiveSum = fiveSum + nums[i]
            elif nums[i]%3 == 0:
                three = three + [nums[i]]
                threeSum = threeSum + nums[i]
        if (totalSum%2==1):
            print("false")
        elif (fiveSum == totalSum/2) & (threeSum == totalSum/2):
            print("true")
        else:
            resList = []
            for i in range(n):
                if nums[i] not in (five+three):
                    resList.append(nums[i])
            resList.sort()
            target=totalSum//2-fiveSum
            res=[]
            search(resList, target)
            if len(res):
                print("true")
            else:
                print("false")
    except:
        break

发表于 2020-08-12 00:36:02 回复(0)
Python
牛客596255372号头像 牛客596255372号
比较基础的做法，
1-先分类整除5和整除3，以及其他类型，三个分类，三个数组
2-求出包含其他的类型的所有子集，不含空集
3-每次求出一个子集，则比对子集和，以及剩余子集和，是否符合和前两个数组，能凑成和相等的两个数组，看代码： 
while True:
    try:
        in1=int(input())
        in2=list(map(int,input().split()))
        res1=[]#三个数组
        res2=[]
        res3=[]
        for i in in2:
            if i%5==0:
                res1.append(i)
            elif i%3==0:
                res2.append(i)
            else:
                res3.append(i)
        sum1=sum(res1)#两个和
        sum2=sum(res2)
        flag1=False#找到后退出的标记
        if sum1>sum2:##标记大小，方便组合
            flag=True
        else:
            flag=False
        for x in range(len(res3)):
            for y in range(x+1,len(res3)+1):#遍历输出所有子集
                sum_temp1=sum(res3[x:y])
                sum_temp2=sum(res3)-sum_temp1
                if not sum_temp1>sum_temp2:#开始比对
                    sum_temp1,sum_temp2=sum_temp2,sum_temp1
                if flag:
                    if sum1+sum_temp2==sum2+sum_temp1:
                        print('true')
                        flag1=True#退出标记
                        break
                else:
                    if sum1+sum_temp1==sum2+sum_temp2:
                        print('true')
                        flag1=True
                        break
            if flag1:#判断标记，因为break只能退出一层
                break
        if not flag1:#判断标记
            print('false')
    except:
        break


发表于 2020-07-30 15:58:19 回复(0)
Python
露露无味头像 露露无味
while True:
    try:
        a=int(input())
        data=map(int, input().strip().split())
        fives=0
        threes=0
        others=0
        ol=[]
        q,p=[],[]
        for i in data:
            if i%5 == 0:
                fives+=i
            elif i%3 == 0:
                threes+=i
            else:
                others+=i
                ol.append(i)
        for x in ol:
            if x > 0:
                p.append(x)
            else:
                q.append(x)
        if len(p) == 0:
            sp=0
        else:
            sp=sum(p)
        if len(q) == 0:
            sp=0
        else:
            sq=sum(q)
        if (fives - threes + others)%2 != 0 or (others+threes-fives)%2 != 0:
            print("false")
        else:
            if fives < threes:
                fives, threes = threes, fives
            if fives - sp + sq > threes:
                print("false")
            else:
                print("true")
    except:
        break

编辑于 2020-07-19 13:46:21 回复(0)
Python
上大-黄志栋头像 上大-黄志栋
这题不是那么容易。最开始理解错题意了，以为不符合条件的元素不要了，直接比较3的倍数的一组和5的倍数一组的和是否相等。后面看讨论区发现不符合条件的元素也要用起来，分配到3和5两组中，使最终和相等。
那么这一题其实还是需要动态规划或者递归的。可以先分析一下，将a作为3的倍数的一组，b作为5的倍数的一组，c作为剩余元素一组。因为sum(a)和sum(b)有差，所以问题成为，如何将一个数组分成两部分，使得两部分的差为一定值。
设sa = sum(a);
sb = sum(b);
sc = sum(c);
则将数组c分成两部分，c1和c2使得（两部分和分别为sc1，sc2）：sa+sc1 = sb +sc2
所以sc1 - sc2 = sb - sa = cha（一个定值）
因为c1与c2所有元素和是sc：sc1 + sc2 = x + (x + cha) = sc ；即x = (sc - cha)/2。其实这里做的时候需要注意，sc-cha必须为偶数，如果不是偶数说明拆分不了两部分，直接本题答案就是false，各位可以仔细想想是不是这么回事。
最终问题是：从数组c中选若干元素，使得和为x，能找到返回true，否则false。
我用的是递归算法，遍历数组c每个元素，因为每个元素都有加与不加两种选择（也可以用动态规划，背包问题思想） 
def dp(c, i, s, aim):
    if s == aim: return True
    if i == len(c):
        return s == aim
    return dp(c, i+1, s, aim) or dp(c, i+1, s+c[i], aim)
while True:
    try:
        n,a,b,c = int(input()),[],[],[]
        data = list(map(int, input().split()))
        for x in data:
            if x%5 == 0: a.append(x)
            elif x%3 == 0: b.append(x)
            else: c.append(x)
        aim = sum(c)-abs(sum(a)-sum(b))
        if aim%2 != 0: print('false')
        else: print('true' if dp(c, 0, 0, aim//2) else 'false')
    except:
        break


编辑于 2020-07-18 15:47:09 回复(0)
Python
牛客533698474号头像 牛客533698474号
可以把问题简化成查找数字之和为特定数的问题
先把5和3的倍数找出来，剩下的数要满足条件就需要每边的和为(总和-3与5倍数的和差)/2 
#!/usr/bin/env python

def search_sum(num_list, sum, deep = 0):
    '''
    在列表num_list中查找组合，之和为sum
    '''
    ret = False
    for v in num_list:
        if sum == v:
            # 当前数就与和相等，不需要查找子列表了
            ret = True
            break

        sub_list = num_list.copy()
        sub_list.remove(v)
        sub_sum = sum - v
        if not len(sub_list)&nbs***bsp;min(sub_list) > sub_sum:
            # 子列表中最小的比需要的和还大，跳过进入下个循环
            ret = False
            continue
        sub_ret = search_sum(sub_list, sub_sum, deep + 1)
        if sub_ret:
            # 子列表中满足和
            ret = True
            break
        
    return ret

def main():
    '''
    先把5和3的倍数找出来，求和sum_5、sum_3
    如果剩下的可以分组，则分组之和必须是sum_one = (sum_left + abs(sum_5 - sum_3)) / 2
    然后找出和为sum_one的数
    '''
    num_cnt = int(input())
    num_list = list(map(int, input().split()))
    num_list_left = list()
    sum_diff = 0
    for v in num_list:
        if v % 5 == 0:
            sum_diff += v
        elif v % 3 == 0:
            sum_diff -= v
        else:
            num_list_left.append(v)
    ret = False
    if (sum(num_list_left) + abs(sum_diff)) % 2 == 0:
        sum_one = int((sum(num_list_left) + abs(sum_diff)) / 2)
        ret = search_sum(num_list_left, sum_one)
    else:
        ret = False

    return ret

while True:
    try:
        print(str(main()).lower())
    except KeyboardInterrupt:
        break
    except EOFError as e:
        break
    except Exception as e:
        print(e)
        break


发表于 2020-07-15 01:15:39 回复(0)
Python
牛客541939069号头像 牛客541939069号 
def search(resList,subSum):
    if subSum == 0:
        return True
    if resList == []:
        return False
    m1 = search(resList[1:],subSum-resList[0])
    m2 = search(resList[1:],subSum)
    return (m1&nbs***bsp;m2)

while True:
    try:
        n = int(input())
        nums = list(map(int,input().split()))
        five = []
        three = []
        totalSum = 0
        fiveSum = 0
        threeSum = 0
        for i in range(n):
            totalSum = totalSum + nums[i]
            if nums[i]%5 == 0:
                five = five + [nums[i]]
                fiveSum = fiveSum + nums[i]
            elif nums[i]%3 == 0:
                three = three + [nums[i]]
                threeSum = threeSum + nums[i]
        if (totalSum%2==1):
            print("false")
        elif (fiveSum == totalSum/2) & (threeSum == totalSum/2):
            print("true")
        else:
            resList = []
            for i in range(n):
                if nums[i] not in (five+three):
                    resList = resList + [nums[i]]
            find = search(resList,totalSum/2-fiveSum)
            if find:
                print("true")
            else:
                print("false")
    except:
        break


编辑于 2020-07-07 23:14:49 回复(0)
Python
牛客885094706号头像 牛客885094706号 
def canequalsum(nums):
    if not nums:
        return 'true'
    if sum(nums) % 2 :
        return 'false'
    #分组
    sum5 = [x for x in nums if x % 5 == 0]
    sum3 = [y for y in nums if y not in sum5 and y % 3 == 0]
    num = [x for x in nums if x not in sum5 and x not in sum3]
    sumtotal = sum(nums)
    if (sumtotal - 2 * sum(sum5)) % 2 != 0&nbs***bsp;(sumtotal - 2 * sum(sum3)) % 2 != 0:
        return 'false'
    else:
        target = (sumtotal - 2 * sum(sum5)) // 2
        if target == 0:
            return 'true'
        ans = []
        canmeet(num,target,0,[],ans)
        if ans:
            return 'true'
        else:
            return 'false'
        
def canmeet(num,target,start,temp,ans):
    if target == 0:
        ans.append(temp[:])
        return ans
    for i in range(start,len(num)):
        temp.append(num[i])
        res = target - num[i]
        canmeet(num,res,i + 1,temp,ans)
        temp.pop()

          
while True:
    try:
        n = input()
        nums = [int(x) for x in input().split()]
        print(canequalsum(nums))
    except:
        break
首先分组，分组后确定目标值，利用回溯法找到可行值
发表于 2020-07-07 10:51:07 回复(0)
Python
昨夜小楼糊东风头像 昨夜小楼糊东风 
def f(x,z):
    if x in z:
        return True
    else:
        total=False
        for i in range(len(z)):
            xx=z[i]
            yy=z.copy()
            yy.remove(xx)
            total=total&nbs***bsp;f(x-xx,yy)
        return total
while True:
    try:
        n=int(input())
        l1=list(map(int,input().split()))
        a=0
        b=0
        c=[]
        d=0
        for i in range(len(l1)):
            d+=l1[i]
            if l1[i]%5==0:
                a+=l1[i]
            elif l1[i]%3==0:
                b+=l1[i]
            else:
                c+=[l1[i]]
        if d%2!=0:
            print('false')
        else:
            if f(int(d/2-b),c):
                print('true')
            else:
                print('false')
    except:
        break

简单的DFS，将数组先分成能被5整除的a，和只能被3整除的b,以及其他部分的c，最后要求的将整体数组分成值相等的两部分，实际上每一部分的值为整体和d的一半，那么，问题就化简为了，d/2-b 或者 d/2-a 能不能由c中的某些数求得。适当剪枝。
发表于 2020-06-17 16:06:36 回复(0)
Python
一直爬的蜗牛头像 一直爬的蜗牛 
def search(list,target):
    if target == 0:
        return True
    if not list:
        return False
    return search(list[1:],target) or search(list[1:],target - list[0])

while True:
    try:
        n = int(input())
        num = list(map(int,input().split()))
        a, b, c = [], [], []
        
        for i in num:
            if i % 5 == 0:
                a.append(i)
            elif i % 3 == 0:
                b.append(i)
            else:
                c.append(i)
        
        t = abs(sum(a) - sum(b))
        d = sum(c) - t
        if d % 2 != 0:
            print("false")
        else:
            if search(c,d/2):
                print("true")
            else:
                print("false")
    except:
        break

编辑于 2020-05-13 23:20:15 回复(0)
提交观点

问题信息

字符串 递归
难度：
23条回答 40224浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号