第二题

[编程题]第二题

热度指数：8151 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

一个数组中有若干正整数，将此数组划分为两个子数组，使得两个子数组各元素之和a,b的差最小，对于非法输入应该输出ERROR。

输入描述:

数组中的元素

输出描述:

降序输出两个子数组的元素和

示例1

输入

10 20 30 10 10
10 20 abc 10 10

输出

40 40
ERROR

算法知识视频讲解

Python

寒风雪蝶

python 是不是输入输出有问题啊，我去掉输入循环，有1%的通过率，加上输入循环，直接报超时0%通过率，算法复杂度也不高啊。。。

import sys

def DFS(num_array,result_half,num_index,tmp_sum):
    if tmp_sum==result_half:
        return tmp_sum
    if num_index==len(num_array):
        return tmp_sum
    
    tmp_sum2=DFS(num_array,result_half,num_index+1,tmp_sum)
    if (tmp_sum+num_array[num_index])<=result_half:
        tmp_sum1=DFS(num_array,result_half,num_index+1,tmp_sum+num_array[num_index])
        if tmp_sum1<tmp_sum2:
            return tmp_sum2 
        else:
            return tmp_sum1
    else:
        return tmp_sum2

def check_num(num_str):
    for a in num_str:
        if a not in '1234567890 \n':
            return False
    return True
    
        
    
    
    


while True:
    
    num_str=sys.stdin.readline()
    if not num_str:
        break
    if check_num(num_str)==False:
        print('ERROR')
        continue
    num_array=list(map(int,num_str.split()))
    result=DFS(num_array,sum(num_array)/2,0,0)
    print(sum(num_array)-result,result)

发表于 2020-08-23 09:52:08 回复(0)