做最便宜的菜
做最便宜的菜
提问于 2022-12-01 15:59:52
在“割断”邻域的绝对差之和最小的直线上，“切割”一个整数矩阵。
示例
考虑到这个矩阵：
1 2 -4
5 -1 3
2 -2 0它可以在四个地方剪切，这里用字母A-D显示：
A B
╷ ╷
1 ╎ 2 ╎ -4
C ---╎----╎----
5 ╎ -1 ╎ 3
D ---╎----╎----
2 ╎ -2 ╎ 0
╵ ╵ 在一条线上削减的成本是在这条线上互相对立的数字的绝对差异之和。例如，削减B将花费\lvert 2--4\rvert+\lvert-1-3\rvert+\lvert-2-0\rvert=12。
但是，您的任务是找到最便宜的裁剪，在本例中是D：\lvert 5-2\rvert+\lvert-1- -2\rvert+\lvert 3-0\rvert=7。
输入
输入将是任何合理格式的整数的二维矩阵.它总是至少有两行和至少两列，而且可能不是正方形的。
输出
输出可以是下列之一：
- 两个独立的矩阵表示切割后的原始矩阵的“部分”，以任何合理的格式。这两个矩阵可以按任一顺序排列，但必须与原始矩阵中的形状相同。
- 以任何合理的格式表示剪切位置的表达式，如上面的
D或等效的索引3(基于0)或4(基于1)。你可以发明你自己的索引方案，但是它必须在你的答案中被描述，并且是一致的。
规则
测试用例
Input
8 1 2 -3
6 -2 -7 -4
-1 -6 -9 3
Output
x
8 1 ╎ 2 -1
6 -2 ╎ -7 -4
-1 -6 ╎ -9 3
╵Input
2 -2 1
8 7 -7
-9 5 -3
0 -8 6
Output
2 -2 1
x---------
8 7 -7
-9 5 -3
0 -8 6
and/or
2 -2 1
8 7 -7
x---------
-9 5 -3
0 -8 6回答 9
Code Golf用户
发布于 2022-12-01 17:57:44
Excel，321个字节
高尔夫代码：
Sub z()
With ActiveSheet.UsedRange
m=-1
x=.Rows.Count
y=.Columns.Count
For c=2To y
t=0
For r=1To x
t=t+Abs(Cells(r,c)-Cells(r,c-1))
Next
If m=-1Then m=t
If t <= mThen m=t:Set a=.Columns(c)
Next
For r=2To x
t=0
For c=1To y
t=t+Abs(Cells(r,c)-Cells(r-1,c))
Next
If t<mThen m=t:Set a=.Rows(r)
Next
a.Insert
End With
End Sub格式化和注释代码：
Sub z()
' Using With for the entire procedure saves plenty of bytes.
With ActiveSheet.UsedRange
' Set the initial minimum to -1 so we can tell when it hasn't been changed yet.
' We could possibly set this (2^1023*1.99) or something but then there'd be some weird edge case where this would fail to cut at the right place.
m = -1
' Save the number of rows and columns now to save bytes later.
x = .Rows.Count
y = .Columns.Count
' Loop through each column, starting with the second column and looking to the left.
For c = 2 To y
' Calculate the cut cost for this column.
t = 0
For r = 1 To x
t = t + Abs(Cells(r, c) - Cells(r, c - 1))
Next
' Check if the min is still the initial value and change it.
If m = -1 Then m = t
' If the total is <= the current minimun, then save it as the new minimum.
' We have to use <= here because "a" is not set in the line above.
If t <= m Then m = t: Set a = .Columns(c)
Next
' Repeat everything we just did but go row by row instead and don't worry about the initial min value.
For r = 2 To x
t = 0
For c = 1 To y
t = t + Abs(Cells(r, c) - Cells(r - 1, c))
Next
If t < m Then m = t: Set a = .Rows(r)
Next
' Insert a row or column as needed. This will default to shifting rows and and columns to the right.
a.Insert
End With
End Sub输入格式：
从活动工作表的单元格A1开始，以每个单元格输入一个数字的矩阵。
输出格式：
代码将在正确的位置插入一行或列，裁剪数据。这相当于输出选项1，就像现在写问题的方式一样。
Code Golf用户
发布于 2022-12-01 19:02:25
J，23字节
(=<./)@,&(1#.2|@-/\])|:输出
输出是“所有可能的水平切割”和“所有可能的垂直切割”的布尔列表。例如，如果输入为3x4矩阵，则输出的长度为5，应解释为：
the first vertical cut is minimal
v
0 0 | 1 0 0
^^^
neither horizontal cut is minimal如果输出中有多个输出，则所有这些都是最小的。
how
- 输入和转置的
...|:。 &(1#.2|@-/\])取每对行，取元素间差异的绝对值，并进行和,将这些结果放在一起，将水平结果放在第一位(=<./)用1标记每一个等于最小值的地方
Code Golf用户
发布于 2022-12-01 19:57:13
果冻，9 字节数
,ZạƝ€§NŒM一种一元链接，它接受列表列表，并生成所有可能的最小裁剪的列表，其中每一个都是一对数字，(1-索引)索引在(整数、两个或更大的)之前被裁剪，以及一个方向指示符，如果索引正在计数行，则为1，如果是计数列，则为2 --例如，[5,2]的意思是在第五列之后削减。
在网上试试！
怎么做？
,ZạƝ€§NŒM - Link: list of lists, M
Z - transpose (M)
, - (M) paired with (that)
€ - for each:
Ɲ - for neighbours:
ạ - (left) absolute difference (right) (vectorises)
§ - sums (vectorises at depth 1)
N - negate
ŒM - maximal multi-dimensional indices页面原文内容由Code Golf提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://codegolf.stackexchange.com/questions/255069
复制相关文章
相似问题
腾讯云开发者
