Grid Reconstruction
题面翻译
题目描述
在一个 \(2×n\) 的网格中 （\(n\) 为偶数），标记 \(1,2,\ldots,2n\)，但每个数只能被使用 \(1\) 次。
某条路径是从 \((1,1)\) 开始的单元序列，随后不断地向下走或向右走，直到到达 \((2,n)\)。注意：这条路径不能超出网格的边界。
通过这条路径的成本是这条路径所通过的单元格上的数字交替和，即，设路径上的数为 \(a,a_1,a_2,\ldots,a_k\)（它是第几个被标记到的，它的下标就是几），则通过这条路径的成本就是 $ a_1 - a_2 + a_3 - a_4 + \ldots = \sum_{i=1}^k a_i \cdot (-1)^{i+1} $。
你需要求一个在网格中标记 \(1,2,...,2n\) 的方案，最大化成本最小的路径的成本。如果有多个答案，你可以输出任意一个。本题中，每个测试点包含 \(t\) 组数据。
输入格式
第一行包含 \(t\)（\(t\) 是测试数据组数）。
随后的 \(t\) 行，每行给出一个 \(n\)，表示网格的边长。
数据保证 \(n\le10^5\)。
输出格式
共 \(2t\) 行，每组测试数据两行，每行包含 \(n\) 个整数，表示所需的网格。如果有多个答案，你可以输出任意一个。
说明/提示
在第一组测试数据中，只有两条从 \((1,1)\) 到 \((2,2)\) 的路径，它们的成本分别是 \(3-1+4=6\) 和 \(3-2+4=5\)，其中成本更小的方案是 \(5\)，这是最优的方案。
在第二组测试数据中，有四条从 \((1,1)\) 到 \((2,4)\) 的路径，它们的成本分别是 \(8-1+5-3+7=16\)，\(8-2+5-3+7=15\)，\(8-2+6-3+7=16\) 和 \(8-2+6-4+7=15\)，其中成本最小的一种方案是 \(15\)，这是最优的方案。
题目描述
Consider a $ 2 \times n $ grid, where $ n $ is an even integer. You may place the integers $ 1, 2, \ldots, 2n $ on the grid, using each integer exactly once.
A path is a sequence of cells achieved by starting at $ (1, 1) $ , then repeatedly walking either downwards or to the right, and stopping when $ (2, n) $ is reached. The path should not extend beyond the grid.
The cost of a path is the alternating sum of the numbers written on the cells in a path. That is, let the numbers written on the cells be $ a_1, a_2, \ldots, a_k $ (in the order that it is visited), the cost of the path is $ a_1 - a_2 + a_3 - a_4 + \ldots = \sum_{i=1}^k a_i \cdot (-1)^{i+1} $ .
Construct a way to place the integers $ 1, 2, \ldots, 2n $ on the grid, such that the minimum cost over all paths from $ (1, 1) $ to $ (2, n) $ is maximized. If there are multiple such grids that result in the maximum value, output any of them.
输入格式
The first line contains a single integer $ t $ ( $ 1 \leq t \leq 1000 $ ) — the number of test cases. The description of test cases follows.
The first and the only line of each test case contains a single integer $ n $ ( $ 2 \leq n \leq 10^5 $ , $ n $ is even) — the number of the columns in the grid.
It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^5 $ .
输出格式
For each test case, output $ 2 $ lines, each containing $ n $ integers — the desired grid. If there are multiple solutions, output any of them.
样例 #1
样例输入 #1
3
2
4
6
样例输出 #1
3 2
1 4
8 2 6 4
1 5 3 7
11 5 9 1 7 3
6 10 2 8 4 12
分析
贪心的思想, 要使得最小代价在所有方案里最大, 那么肯定要让加的数尽可能的大, 而通过观察可以发现:
- 第一行的奇数位比如(1, 1), (1, 3), (1, 5).... 是一定是加数, 偶数位一定是减数
- 第二行则刚好相反
- (1, 1) 和 (2, n) 分别是起点和终点, 是一定会被加上的
所以我们要把最大的两个数放在 (1, 1) 和 (2, n)上, 然后小的数放在减数的位置, 大的数放在加数的位置
贪就要贪到底, 大体原则已经确定了, 就剩下除了起点和终点怎么放了, 要使得相邻差最大, 肯定要让相邻的数的奇偶性一致, 就比如都要放小的数, n - 1 肯定大于 n - 2, 且相邻数之间, 大的尽可能大, 小的尽可能小, 那我们就得出这样一个构造方案:
-
第一行: 1(指位置1) 放最大的奇数, 3放次大的奇数...以此类推
2放最小的奇数, 4放次小的奇数...以此类推
-
第二行: n 放最大的偶数, n - 2 放次大的偶数....以此类推
n - 1 放最小的偶数, n - 3 放次小的偶数...以此类推
代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int f[3][N];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int t; cin >> t;
while (t--)
{
int n; cin >> n;
f[1][1] = 2 * n - 1, f[2][n] = 2 * n;
int p = 1, q = 2 * n - 3;
for (int i = 2; i <= n; i += 2)
{
//i是减数位, i + 1是加数位
f[1][i] = p;
p += 2;
f[1][i + 1] = q;
q -= 2;
}
p = 2, q = 2 * n - 2;
for (int i = n - 1; i >= 1; i -= 2)
{
//i是减数位, i-1是加数位
f[2][i] = p;
p += 2;
f[2][i - 1] = q;
q -= 2;
}
for(int i = 1; i <= 2; i ++)
{
for (int j = 1; j <= n; j++)
{
cout << f[i][j] << ' ';
}
cout << endl;
}
}
}