她卖避难所

Question

一场巨大的风暴正在肆虐着这个世界，当你和你的家人逃离它时，你遇到了一个由一个女孩经营的巨大的避难所。她告诉你，“她出售避难所”，不同类型的房间提供不同的价格。

一个房间只能容纳一个人。

挑战

编写一个包含两个输入的程序:居住在避难所的人数和数组、地图、对象或字符串，只要结构类似于：

[[2, 3], [3, 5], [6, 7]]

在本例中，它是一个二维数组，但它可能是一个字符串，如

2,3 3,5 6,7

对于每一项，第一项是为这种类型提供的房间数目，第二项是一个房间的费用。例如,

[[1, 2], [3, 4]]

这意味着第一种类型的房间每人提供2美元，第二种类型有3间，每间4美元。

由于您的家庭资源有限，您希望找到尽可能少花钱的配置。因此，您的程序应该输出一些包含房间数量信息的数字。最后，它还应该输出总成本。

这可能听起来很混乱，所以以一个示例输入为例：

First input: 5
Second input: [[2, 5], [2, 3], [7, 100]]

最便宜的可能配置是让两个人留在第一种类型中，花费3 * 2 = 6美元，然后两个人在第二种类型中使用5 * 2 = 10美元，另一种人在最后一种类型中使用100 * 1 = 100美元。因此，总成本是116美元。这个测试用例的输出将是

2 // two people in the first type of room
2 // two people in the second type of room
1 // one person in the third type of room
116 // total cost

让我们再试一次。

first input: 10
second input: [[1340993842, 5500], [1, 5000]]

最便宜的配置是让一人留在第二种类型，而其他九人在第一种类型。因此，成本是9 * 5500 + 1 * 5000 = 54500。输出：

9
1
54500

一些额外的规则：

• 住在这里的人数永远不会超过房间总数。
• 标准的漏洞和往常一样是不允许的。
• 最后的产出必须是价格。
• 如果愿意，可以将其作为数组输出。
• 没有其他人住在避难所里。
• 最短的答案(以字节为单位)获胜，因为这个问题是密码-高尔夫。
• 输入可以作为rest参数。
• 订单可能会倒转，例如价格可能是第一项。不过，你必须说清楚。
• 这些房间不能保证从最便宜到最贵的地方订购。
• 输出必须按照给定类型的顺序进行。

Answer 1

JavaScript (ES6)，104个字节

由于@tsh保存了5个字节

期望(list)(n)，其中列表由[available_i, price_i]对组成。

返回[[booked_1, ..., booked_N], total_cost]。

(p,o=p.map(_=>s=0))=>g=n=>n?g(n-1,p.find(([k,c],i)=>k*!p.some(([K,C])=>K&&C<c)&&++o[s+=c,i])[0]--):[o,s]

在网上试试！

评论

( p,                        // outer function taking the list p[]
  o = p.map(_ => s = 0)     // o[] = booking array, initialize to 0's
                            // s = total cost
) =>                        //
g = n =>                    // g is a recursive function taking the number of people n
  n ?                       // if there's still at least one room to book:
    g(                      //   do a recursive call:
      n - 1,                //     decrement n
      p.find(([k, c], i) => //     look for a room [k, c] at position i:
        k *                 //       if it is still available
        !p.some(([K, C]) => //       and there is not another room type
          K && C < c        //       that is cheaper and still available
        ) &&                //       then:
          ++o[s += c, i]    //         increment o[i] (i.e. book a room with index i)
                            //         and add c to the total cost
      )                     //     end of find() (guaranteed to be successful)
      [0]--                 //     decrement the number of available rooms of this type
    )                       //   end of recursive call
  :                         // else:
    [o, s]                  //   stop the recursion and return the results

Answer 2

R，95字节

function(n,l)list(rowSums(outer(l[2,],y<-sort(unlist(Map(rep,l[2,],l[1,])))[1:n],`==`)),sum(y))

在网上试试！

Answer 3

Python 3.8，108个字节

输入是[number, price]对的列表。已预订房间的数量被打印出来，总价格被退回。

f=lambda p,r:p and(print(w:=min((X:=r.pop(0))[0],max(0,p-sum(x for x,y in r if y<X[1]))))or w*X[1]+f(p-w,r))

在网上试试！