V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
codechaser
V2EX  ›  程序员

求解答一道算法题

  •  
  •   codechaser · 2019-09-22 21:36:58 +08:00 · 3989 次点击
    这是一个创建于 1649 天前的主题,其中的信息可能已经有所发展或是发生改变。

    /**

    • 给定一个数组及其长度 n,每次在这 n 个数字中选取一个数 x,
    • 然后取出数组中值为 x 的所有数,获得的资源是 x*值为 x 的元素个数;
    • 同时删去刚好值小于(就是刚好比他小))和大于 x(刚好比他大一点)的所有数;
    • 然后开始下一轮,直到数组为空。请问能获得的最大资源是? */

    求问这道题怎么做?

    28 条回复    2019-09-24 15:56:26 +08:00
    geelaw
        1
    geelaw  
       2019-09-22 21:56:19 +08:00 via iPhone   ❤️ 1
    最直接的思路是区间动态规划,自然需要的时间是 n^3,空间是 n^2。
    稍微思考可以只考虑开头的区间,时间是 nlogn,额外空间是 1。

    具体做法留作习题。
    yidinghe
        2
    yidinghe  
       2019-09-22 22:25:12 +08:00
    看不懂,数组为 [1] 的话,删除比 1 小和比 1 大的数之后,还剩下 [1] ,岂不是永远不会为空?
    Yang2096
        3
    Yang2096  
       2019-09-22 23:21:37 +08:00
    @yidinghe 第二句里面的“取出”大概是先把值为 x 的数全删掉的意思吧
    fxxwor99LVHTing
        4
    fxxwor99LVHTing  
       2019-09-22 23:32:56 +08:00
    没看懂。这是原题吗?
    第二句,‘获得的资源是 x*值为 x 的元素个数’ 中 ‘x*值’ 是什么意思?(第二句可能是病句)
    第三句中的 ‘刚好’ 具体是什么意思呢?数组中的元素全部由整数组成,还是也可以允许浮点数?
    yidinghe
        5
    yidinghe  
       2019-09-23 01:22:58 +08:00 via Android
    唉,理科生的表达能力
    RecursiveG
        6
    RecursiveG  
       2019-09-23 04:47:43 +08:00
    把原数组预处理成两个长度为 k 的数组 a[i=1..k]:=第 i 大的数,b[i=1..k]:=a[i]出现的次数。然后从 1 到 k 做 DP。没有证明,不保证对。
    brainfxxk
        7
    brainfxxk  
       2019-09-23 05:26:33 +08:00
    @geelaw
    @RecursiveG
    请教下,按 w[i]=(值*次数)并按值排序预处理之后。假设此序列为 w 长度为 m,操作数次数为 m/3。则我可以从 w 中取任意 m/3 个元素,只要不取首尾两个元素且取到的元素在 w 中不相邻即可对吗?
    zjsxwc
        8
    zjsxwc  
       2019-09-23 07:29:02 +08:00 via Android
    动态规划,
    由于与数组顺序无关于是可以,定义 数组解 A 为 X(n)+ Y(m)+... 其中 X、Y 为数组里数的值,n、m 为数 X、Y 分别出现的次数。

    于是状态转移方程为
    A(XnYm)=max(X*n-m+A(Ym), Y*m-n+A(Xm))
    ...
    依次类推
    codechaser
        9
    codechaser  
    OP
       2019-09-23 07:43:06 +08:00 via Android
    @fxxwor99LVHTing 比如 1 3 4 5 3 6 4 3,这个第一次我取 3,里面有两个 4,那么这次的资源值最大是 4*4,,然后把 4,3 和 5 全去掉,只剩下了 1,6 了,在继续取,这时就取 6,把 1 去掉。总得资源是 4*4+6
    codechaser
        10
    codechaser  
    OP
       2019-09-23 07:45:08 +08:00 via Android
    打错了,第一个应该是 3*3,不是 4*4,有三个 3 和两个 4,选 3*3 而不选 4*2。再去掉 3 和 5,只剩 1 6
    codechaser
        11
    codechaser  
    OP
       2019-09-23 07:46:59 +08:00 via Android
    @yidinghe 理解一下,这题当时做笔试的时候是一大段文字,我做的时候随手记的。
    zjsxwc
        12
    zjsxwc  
       2019-09-23 07:47:15 +08:00 via Android
    动态规划,
    由于与数组顺序无关于是可以,定义 数组解为 A(XnYm) 其中 X、Y 为数组里数的值,n、m 为数 X、Y 分别出现的次数。

    于是状态转移方程为
    A(Xn)=X*n
    A(XnYm)=max(X*n-m+A(Ym), Y*m-n+A(Xm))
    A(XnYmZa)=max(X*n-m-a+A(YmZa), Y*m-n-a+A(XmZa), Z*a-n-mA(XnYm))
    ...
    依次类推
    codechaser
        13
    codechaser  
    OP
       2019-09-23 07:49:04 +08:00 via Android
    @fxxwor99LVHTing 刚好就是说在这个数组里比你取出的元素正好大的。
    zjsxwc
        14
    zjsxwc  
       2019-09-23 07:55:11 +08:00 via Android
    @zjsxwc #12 原文:“动态规划,由于与数组顺序无关于是可以,定义 数组解为 A(XnYm) 其中 X、Y 为数组里数的值,n、m 为数 X、Y 分别出现的次数。于是状态转移方程为 A(Xn)=X*nA(XnYm)=max(X*n-m+A(Ym), Y*m-n+A(Xm))A(XnYmZa)=max(X*n-m-a+A(YmZa), Y*m-n-a+A(XmZa), Z*a-n-m+A(XnYm))...依次类推”


    感觉复杂度还是 n^3 等大神解答吧

    回复:
    codingBug
        15
    codingBug  
       2019-09-23 09:24:42 +08:00
    瑟瑟发抖
    Vegetable
        16
    Vegetable  
       2019-09-23 09:31:40 +08:00
    @yidinghe 求别黑理科生表达能力吧,理科生描述个题目应该是清清楚楚才对
    RecursiveG
        17
    RecursiveG  
       2019-09-23 09:45:22 +08:00
    接 #6
    再令 p[1]:=a[1]*b[1], u[0]:=0
    p[1<i<=k]:=u[i-1]+a[1]*b[1]
    u[1<i<=k]:=max(u[i-1],p[i-1])
    结果为 max(u[k],p[k])
    RecursiveG
        18
    RecursiveG  
       2019-09-23 09:46:31 +08:00
    更正 #17
    再令 p[1]:=a[1]*b[1], u[1]:=0
    p[1<i<=k]:=u[i-1]+a[i]*b[i]
    u[1<i<=k]:=max(u[i-1],p[i-1])
    结果为 max(u[k],p[k])
    wolfish
        19
    wolfish  
       2019-09-23 11:11:49 +08:00
    其实就是一个普通 01 背包问题。
    假设 n 个数里有 m 种数值,将这 m 种数值从小到大排序,并记每种数值的价值为 val[i]=值本身*个数
    i:1~m
    然后就是 dp 定义。
    dp[i][0]:前 i 种数,不选入第 i 种数值,所获得的最大价值
    dp[i][1]:前 i 种数,选入第 i 种数值,所获得的最大价值。
    dp[i][0] = max(dp[i-1][0], dp[i-1][1])
    dp[i][1] = dp[i-1][0]+val[i]
    最终结果就是 max(dp[m][0], dp[m][1])
    no1xsyzy
        20
    no1xsyzy  
       2019-09-23 13:43:46 +08:00
    @brainfxxk #7 只需要不相邻,个数无限制,最多可以 ceiling(n/2)
    layorlayor
        21
    layorlayor  
       2019-09-23 14:43:57 +08:00
    对于一个数 x, 它有 cx 个。比他小的最大数是 y,有 cy 个。比他大的最小数是 z,有 cz 个。 那是不是按照 x * cx - y * cy - z * cz 降序,然后一个一个挑?
    brainfxxk
        22
    brainfxxk  
       2019-09-23 15:59:20 +08:00
    @no1xsyzy 个数为什么没限制,每次操作会删掉 3 个元素呀。
    no1xsyzy
        23
    no1xsyzy  
       2019-09-23 18:13:49 +08:00
    @brainfxxk 不一定,如果删的是两头的只会删掉两个,如果最后只剩一个只会删掉一个
    brainfxxk
        24
    brainfxxk  
       2019-09-23 18:30:05 +08:00
    @no1xsyzy 啊是的,也就是如果删除的元素不一定需要有前驱和后继,那么总长度也不需要满足 3 的倍数了。
    BiteTheDust
        25
    BiteTheDust  
       2019-09-23 20:10:07 +08:00
    首先可以发现原序列没有用
    我们把每个值来排序 然后根据每个值的出现次数 使得这个值获得一个权值 得到一个新的序列
    显然对于这个新序列 我们不能连续地去取里面的值(也就是说我们取了某个数 就不能取相邻的数)
    这样转化后我们就可以用动态规划来获得最大的总和 如果值域不大复杂度可以达到 O(n) 否则复杂度瓶颈为 nlogn 的排序
    nvioue
        26
    nvioue  
       2019-09-24 00:10:23 +08:00 via Android
    不知所云 上 leetcode 链接吧 求你了
    codechaser
        27
    codechaser  
    OP
       2019-09-24 08:38:16 +08:00
    @nvioue 题目的意思就是给出一个数组,你每次可以选择一个值 x,先删除数组中值为 x 的所有元素,用被删除元素个数 n_x 乘以 x 当做这次拿到的资源值,然后删去数组中正好比 x 大和 x 小的所有元素(如[2,4,4,1,5,3,6,3],x 选 6 的话,总共要删去 6,4,4 这几个元素,资源值为 6。)这样算一次操作,若干次操作后数组会空,问加在一起最大能拿到多少资源值?我不知道这个 leetcode 上有不,这是笔试题,当时就随手记了一下。
    no1xsyzy
        28
    no1xsyzy  
       2019-09-24 15:56:26 +08:00
    @nvioue 简单地说:
    Given X: uint[], n = len(X)
    Require x in X while len(X) > 0
    Do
    X.remove(x)
    X.remove(min(a for a in X if a > x))
    X.remove(max(a for a in X if a < x))
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2996 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 30ms · UTC 14:48 · PVG 22:48 · LAX 07:48 · JFK 10:48
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.