分享到:文章主题: 阿里编程测验算法,组合优化最小
qcomedy楼主
comedy
等级
用户
文章
1080
积分
13067
星座
双子座
发信人: qcomedy (comedy), 信区: ACM_ICPC
标  题: 阿里编程测验算法,组合优化最小
发信站: 北邮人论坛 (Tue Apr 17 21:48:02 2018), 站内

阿里内推编程测试,是一个最优化组合的问题,没有头绪,求大神。
**题目描述:**  
某玩具店内有编号为1-N的卡片多张,且有玩具M种(第i种的价格为Pi)。每种玩具的包装盒内,有编号固定且连续的卡片(Xi至Yi, 1<=Xi<=Yi<=N)各一张。为了促销开展“集卡”活动。活动内容为集齐N种卡片,且对每种卡片有数量要求(规定编号为i的卡片需要Ni张),即可换得优惠券。请问客户至少花多少钱买这些玩具可以得到一张优惠券。(假设M和N均不大于100)

**输入:**
第一行有两个整数N, M,表示卡片的最大编号和玩具的种类。接下来一行中包含N个非负整数,表示活动需要集齐每种卡片的张数。接下来的M行中每行包含三个整数X, Y, P分别表示这种玩具中卡片编号的起始号、终止号和价格。假定每种玩具都是无限多的。  

**输出:**
仅包含一个整数,表示买玩具得到优惠券最少花的费用。

**输入范例:**
4 2
1 3 2 2
1 2 2
2 4 5

**输出范例:**
12
(即买2个5元的,1个2元的)

--

※ 来源:·北邮人论坛 http://bbs.byr.cn·[FROM: 10.205.29.*]
    返回顶部
    upcupc沙发
    温暖的向阳花
    等级
    用户
    文章
    107
    积分
    6254
    星座
    狮子座
    发信人: upcupc (温暖的向阳花), 信区: ACM_ICPC
    标  题: Re: 阿里编程测验算法,组合优化最小
    发信站: 北邮人论坛 (Tue Apr 17 23:21:39 2018), 站内

    ddddddd
    --

    ※ 来源:·北邮人论坛 http://bbs.byr.cn·[FROM: 10.205.29.*]
      返回顶部
      a2013211232板凳
      王木流梦
      等级
      用户
      文章
      22
      积分
      418
      星座
      天秤座
      发信人: a2013211232 (王木流梦), 信区: ACM_ICPC
      标  题: Re: 阿里编程测验算法,组合优化最小
      发信站: 北邮人论坛 (Wed May 16 16:48:13 2018), 站内

      帮顶,求大神解答
      我想了一个超级笨的方法,也不知道可不可行。。**对玩具进行排序,按照玩具内有用的卡和价格的比例进行排序**
      比如例子中第一个玩具是2元,获得2张有用的卡,比例为1元1张;第二个玩具是5元,获得三张有用的卡,比例为1.6元一张;那就优先选择买第一个玩具,一直到该玩具的价值比发生变化。
      比如买了一个玩具1后,待集其卡片数组变为 0 2 2 2。
      此时第一个玩具是2元只能获得1张有用的卡(因为1已经集齐了)第二个玩具价值比还是1.6;所以选择优先买第二个玩具,以此类推。

      m,n都不超过100,如果思路可行的话应该不会超时吧,求大神指教ema23
      --

      ※ 来源:·北邮人论坛 http://bbs.byr.cn·[FROM: 10.108.82.*]
        返回顶部
        a2013211232第3楼
        王木流梦
        等级
        用户
        文章
        22
        积分
        418
        星座
        天秤座
        发信人: a2013211232 (王木流梦), 信区: ACM_ICPC
        标  题: Re: 阿里编程测验算法,组合优化最小
        发信站: 北邮人论坛 (Wed May 16 17:03:59 2018), 站内


        【 在 a2013211232 的大作中提到: 】
        : 帮顶,求大神解答
        : 我想了一个超级笨的方法,也不知道可不可行。。**对玩具进行排序,按照玩具内有用的卡和价格的比例进行排序**
        : 比如例子中第一个玩具是2元,获得2张有用的卡,比例为1元1张;第二个玩具是5元,获得三张有用的卡,比例为1.6元一张;那就优先选择买第一个玩具,一直到该玩具的价值比发生变化。
        : ...................
        行吧,我已经发现我错了,还是没解决我最初想避免的那个问题(有不得不买的玩具然后玩具内附加着一些其它卡片的情况),如果是下面这组数据,答案应该是100 + 99,而之前那种方法会是200。。。
        2 2
        100 1
        1 1 1
        1 2 100
        所以转变思路?从那些不得不买的玩具入手,比如总共只有10个玩具包含第i张卡片,先用我上面那个方法从这10个玩具里面选出来最优的那个,然后再依次类推?我已经迷了
        --

        ※ 来源:·北邮人论坛 http://bbs.byr.cn·[FROM: 10.108.82.*]
          返回顶部
          • 文章数:4 分页:
            1. 1