{"problem":{"name":"矩阵游戏 / matrix","description":{"content":"小山和小西在玩一个矩阵游戏： 有一个 $n\\times m$ 的矩阵，小山可以为每一行选择一个值作为该行的代表值。小西会从这些代表值中选择两个数作差（取绝对值）。 小山希望小西选出的差值尽可能小；小西希望自己选出的差值尽可能大。 请你计算，在两个人都采取最优策略的情况下，小西最终选出的两个代表值的差的绝对值是多少？","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGB4470"},"statements":[{"statement_type":"Markdown","content":"小山和小西在玩一个矩阵游戏：\n\n有一个 $n\\times m$ 的矩阵，小山可以为每一行选择一个值作为该行的代表值。小西会从这些代表值中选择两个数作差（取绝对值）。\n\n小山希望小西选出的差值尽可能小；小西希望自己选出的差值尽可能大。\n\n请你计算，在两个人都采取最优策略的情况下，小西最终选出的两个代表值的差的绝对值是多少？\n\n## Input\n\n第一行两个整数 $n,m$。\n\n接下来 $n$ 行，每行 $m$ 个整数。\n\n## Output\n\n一个整数，表示最终的差值。\n\n[samples]\n\n## Note\n\n#### 【样例 $1$ 解释】\n两人都选择最优策略时，小山选择 $\\{2,4,3\\}$ 作为三行的代表值。在此集合下，小西会选择差值最大的两个数 $2$ 和 $4$，得到的最大差值为 $|4-2|=2$。这是小山能够确保的最小最大差值。\n\n#### 【数据范围】\n对于 $10\\%$ 的数据，保证 $m=1$。\n\n对于另外 $10\\%$ 的数据，保证 $n=2$。\n\n对于另外 $20\\%$ 的数据，保证 $2\\le n\\le8,2\\le m\\le8$。\n\n对于另外 $30\\%$ 的数据，保证 $2\\le n\\le100,2\\le m\\le100$。\n\n对于 $100\\%$ 的数据，保证 $2\\le n\\le1000,1\\le m\\le1000$，矩阵中的整数绝对值不超过 $10^9$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGB4470","tags":["博弈论","2025","O2优化","排序","山西","双指针 two-pointer","科创活动","小学活动"],"sample_group":[["3 3\n1 2 9\n4 5 6\n7 8 3","2"]],"created_at":"2026-03-03 11:09:25"}}