P9656 So I'll Max Out My Constructive Algorithm Skills

模拟

题意简介

在一个 $n\times n$ 的矩阵里面，有一个人要一行一行蛇形爬过去。求一条路径 $l$，使得 $\sum _{i=1}^{n^2-1}{l}_i>l_{i+1}$ 严格小于 $\sum _{i=1}^{n^2-1}{l}_i\le l_{i-1}$。

思路

我们可以枚举每一列，蛇形记录下路径。然后对路径进行枚举，分别记录正着要爬的台阶数量以及反着要爬的台阶数量，取最小值输出路径。

#include <algorithm>
#include <iostream>
#include <vector>
 
using namespace std;
 
const int kMaxN = 65;
 
int a[kMaxN][kMaxN], t, n, c1, c2;
vector<int> v;  // 使用vector记录路径
 
int main() {
  for (cin >> t; t; t--) {
    cin >> n, v.clear(), c1 = c2 = 0;  // 多测记得清空
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        cin >> a[i][j];
      }
    }
    for (int i = 1; i <= n; i++) {
      if (i & 1) {  // 如果是奇数行
        for (int j = 1; j <= n; j++) {  // 正着走过去
          v.push_back(a[i][j]);
        }
      } else {  // 偶数行
        for (int j = n; j >= 1; j--) {  // 反着走过去
          v.push_back(a[i][j]);
        }
      }
    }
    for (int i = 0; i < n * n - 1; i++) { // 注意vector是从零开始的
      v[i] > v[i + 1] ? ++c1 : ++c2;  // c1,c2分别表示反着、正着走过去的台阶数
    }
    if (c1 < c2) {  // 如果反着更优
      for (int i = n * n - 1; i >= 0; i--) {  // 反向输出
        cout << v[i] << ' ';
      }
    } else {
      for (int i = 0; i < n * n; i++) {  // 正着输出
        cout << v[i] << ' ';
      }
    }
    cout << '\n';
  }
  return 0;
}