AcWing 3503. 数组划分
原题链接
简单
作者:
oops1
,
2024-04-22 14:44:05
,
所有人可见
,
阅读 2
C++ 代码
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int n,sum=0,cnt=0,flag=0,mini=0x3f3f3f3f; vector<int> nums;//cnt代表其中一个子数组的和
void dfs(int i,int s){//i代表当前下标,s代表当前和
if(i>n||flag||cnt==sum/2) return;
if(nums[i]>sum/2) {flag=1;cnt=nums[i];return;}//当前元素的值大于一半的总和,这个元素单独一组,其他dfs可以结束
int now=abs(s-(sum-s));//计算当前差值绝对值
if(now<mini) {mini=now;cnt=s;}//更新最小差值,更新答案
if(s>=sum/2) return;//无需后续dfs
dfs(i+1,s+nums[i]);//加上当前元素
dfs(i+1,s);//不加
}
int main()
{
int x;
while(cin>>x){
nums.push_back(x);
sum+=x;
} n=nums.size();
dfs(0,0);
cout<<max(cnt,sum-cnt)<<' '; cout<<min(cnt,sum-cnt)<<' ';//降序输出
}