首页 > 其他分享 >lc2035 将数组分成两个数组并最小化数组和的差

lc2035 将数组分成两个数组并最小化数组和的差

时间:2024-03-14 20:26:30浏览次数:27  
标签:st2 lc2035 int nums dfs 数组 ans 最小化

给你一个长度为2n的整数数组,需要将它分成两个长度为n的数组,分别求出两个数组的和,并最小化两个数组和之差的绝对值。nums中每个元素都需要放入两个数组之一,求最小的数组和之差。
1<=n<=15; -1E7<=nums[i]<=1E7

直接暴搜的话最坏时间复杂度是O(2^30),会TLE,可以使用双向dfs优化,每次dfs各搜一半,然后遍历其中一个集合,到另一个集合找最优解。时间复杂度降为O(2*2^15)

class Solution {
public:
    int minimumDifference(vector<int>& nums) {
        int n = nums.size();
        vector<set<int>> st1(n), st2(n);
        int sum = accumulate(nums.begin(), nums.end(), 0);
        
        auto dfs = [&](auto self, int x, int R, int cnt, int cur, vector<set<int>> &st) -> void {
            if (x == R) {
                st[cnt].insert(2*cur);
                return;
            }
            self(self, x+1, R, cnt, cur, st);
            self(self, x+1, R, cnt+1, cur+nums[x], st);
        };
        
        dfs(dfs, 0, n/2, 0, 0, st1);
        dfs(dfs, n/2, n, 0, 0, st2);
        int ans = INT_MAX;
        for (int k = 0; k < n/2; k++) {
            int u = n/2 - k;
            for (auto i : st1[k]) {
                auto it = st2[u].lower_bound(sum-i);
                if (it != st2[u].end()) {
                    ans = min(ans, abs(i + *it - sum));
                }
                if (it != st2[u].begin()) {
                    --it;
                    ans = min(ans, abs(i + *it - sum));
                }
            }
        }
        return ans;
    }
};

标签:st2,lc2035,int,nums,dfs,数组,ans,最小化
From: https://www.cnblogs.com/chenfy27/p/18073839

相关文章

  • day-19 合并后数组中的最大元素
    思路:从后向前遍历数组,用tans记录每一种可能的最大值,ans为实际最大值。注意:若ans==0,返回nums[0]要用longcodeclassSolution{publiclongmaxArrayValue(int[]nums){longans=0;longtans=0;booleanflag=true;for(in......
  • C++动态数组
    #include<iostream>usingnamespacestd;intmain(){ intt,i=0,j=0; cin>>t; char*pc=nullptr;//初始化 int*pi=nullptr;//初始化 float*pf=nullptr;//初始化 intsum=0; intFLAG=0; while(FLAG<t) { charch; cin>>......
  • 【你也能从零基础学会网站开发】Web建站之javascript入门篇 Array数组
    ......
  • 数组常见操作【最大/最小/数据反转操作】
    importjava.util.Scanner;publicclassday_4_5{publicstaticvoidmain(String[]args){/*数组的常见操作*///遍历int[]arr={3,5,2,1,4};intmax=arr[0];intmax1=0;intmax2=0;for(in......
  • [牛客]小红的数组分配
    题目思路去考虑sort排序为相同数字为偶数个,输出格式错误的去思考了数组为pair代码#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintN=1e6+10;inti,j,k,n,m,t,res,a[N]={0};strings;voidslove(){ cin>>n; for(i=0;i<n*2;i++)ci......
  • C语言:洛谷数组题目(2)(冰雹猜想,校门外的树,旗鼓相当的对手)
    目录1.前言2.三则题目1.冰雹猜想1.题目描述2.输入格式3.输出格式4.题解2.校门外的树1.题目描述2.输入格式3.输出格式4.题解3.旗鼓相当的对手1.题目描述2.输入格式3.输出格式4.题解3.小结1.前言今天小蒟蒻继续为大家分享洛谷数组题单题解,一共三道题,希望大......
  • 滴水逆向笔记系列-c语言总结6-20.多级指针 数组指针 函数指针-21.位运算-22.内存分配
    第二十课c语言13多级指针数组指针函数指针1.多级指针反汇编一二级指针可以看到p1==*(p1+0)==p1[0]本来一直没想懂为什么是movsxecx,byteptr[eax],是byte,才发现p1是char类型,所以才得用movsx拓展(p1+2)==p1[2],指针可以用和[]取值,他们是一样的(((p3+1)+2)+3)==p3[......
  • C语言从入门到实战————数组和指针的深入理解
    前言在C语言中,数组和指针有的密切得联系,因为数组名本身就相当于一个指针常量。指针是一个变量,专门用来存储另一个变量的内存地址,通过这个地址可以访问和操作该变量的值,同时也包括数组。数组是一组连续存储的同类型数据的集合,它允许通过索引快速访问各个元素。同时数组名也是数......
  • leetcode: 2789. 合并数组中的最大元素
    给你一个下标从 0 开始、由正整数组成的数组 nums 。你可以在数组上执行下述操作 任意 次:选中一个同时满足 0<=i<nums.length-1 和 nums[i]<=nums[i+1] 的整数 i 。将元素 nums[i+1] 替换为 nums[i]+nums[i+1] ,并从数组中删除元素 nums[i] ......
  • 【ArcPy】矢量数据与Numpy数组互转
    代码importarcpyinputshp=r"C:\Users\admin\Desktop\excelfile\0.shp"outputshp=r"C:\Users\admin\Desktop\excelfile\copy02.shp"spatial_ref=arcpy.Describe(inputshp).spatialReferencearr=arcpy.da.FeatureClassToNumPyArray(in......