上上下下题解

本题主要考察最短路建模和动态规划的应用。

题意简单归纳为：通过交换两个数组位置相对应的元素，使得第一个数组降序、第二个数据升序的最少交换次数是多少。如果无法达成条件，返回 -1。

20 分的做法

由于 ，我们可以通过二进制枚举每一对位置是否交换，然后跑一遍 的检查看看是否符合要求即可，时间复杂度 ，能够通过。

60 分的做法

如果我们从左往右看作从第一个点出发，走到尾，能生成两条完全对称的路径，那我们就找到了可以走通的办法。所以，我们的问题就变成了寻找一种决策方法，来找到能否生成这样的一条路径且消费最低。

我们先来考虑什么情况下可以交换。

上图的两种情况给我们带来了两个不等式组：满足 B[i+1] < A[i] && B[i] < A[i+1] 时，我们可以交换 A[i] 和 B[i]，同理满足 A[i+1] < A[i] && B[i+1] > B[i] 时我们可以不交换。可以看到，i+1 是否交换影响到了 i，此时的大小关系产生了变化。

我们通过如下建模解决这个问题：将每个位置抽象为两个点：交换和不交换。于是，我们只需要讨论当前点和下一个点在各自交换和不交换情况下的连线关系即可：如果当前位置交换和下一个位置交换后仍然能保证序列合法，我们就连接两个位置的交换点，其他情况同理。而如果当前位置交换了，我们就需要一次交换的代价，所以，从当前位置的交换点出发的路径长度设为 1，而不交换点出发的路径长度为 0。最后，我们准备一个起点向开头的两个点各连接一条长度为 0 的边，而从序列末尾的交换点连一条长度为 1 的边到终点，不交换点连一条长度为 0 的边到终点，跑一次起点到终点的单源最短路即可。使用 Dijkstra 或者 Bellman-Ford 都可以解决。Dijkstra 需要的时间为 ，Bellman-Ford 需要的时间为 ，其中 ，所以两种情况都近似需要 的时间复杂度。

100 分的做法

100 分的做法有两种。

• 最短路优化
  使用邻接表保存这个数据量下的图，然后使用优先队列优化的 Dijkstra 算法可以将时间复杂度优化到 ，近似为 ，能够通过本题。
• 动态规划
  从最短路做法可以看出，实际上我们 i+1 的答案仅受 i 的影响：我们可以在 i 和 i+1 的两种决策中选择代价最小的选择组合到 i+1 上，这便成为了一个经典动态规划过程，设计状态 dp[i][0/1] 为位置 i 交换或不交换的最小代价，转移过程同建边过程类似，这样就可以在 的时间内解决这个问题。

最短路优化的参考实现如下：

class Solution {
  const int INF = 0x3f3f3f3f;

  struct Node {
    int x, w;

    bool operator<(const Node &n) const { return w > n.w; }
  };

  int solve(const vector<int> &a, const vector<int> &b) {
    int n = a.size();

    vector<int> dis(n * 2 + 2, INF);
    vector<vector<Node>> G(n * 2 + 2);

    for (int i = 0; i < n - 1; i++) {
      int change = 2 * i + 1, change_next = 2 * i + 3; // change means exchange
      int keep = 2 * i + 2, keep_next = 2 * i + 4; // keep means do not exchange
      if (a[i] > a[i + 1] && b[i] < b[i + 1]) {
        G[keep].push_back({keep_next, 0});
      }

      if (a[i] > b[i + 1] && b[i] < a[i + 1]) {
        G[keep].push_back({change_next, 0});
      }

      if (a[i] < a[i + 1] && b[i] > b[i + 1]) {
        G[change].push_back({change_next, 1});
      }

      if (a[i] < b[i + 1] && b[i] > a[i + 1]) {
        G[change].push_back({keep_next, 1});
      }
    }

    G[0].push_back({1, 0});
    G[0].push_back({2, 0});

    G[2 * n - 1].push_back({2 * n + 1, 1});
    G[2 * n].push_back({2 * n + 1, 0});

    priority_queue<Node> pq;

    dis[0] = 0;
    pq.push({0, 0});

    while (pq.size()) {
      auto p = pq.top();
      pq.pop();
      int x = p.x;
      if (dis[x] < p.w)
        continue;
      for (auto i : G[x]) {
        if (dis[i.x] > dis[x] + i.w) {
          dis[i.x] = dis[x] + i.w;
          pq.push({i.x, dis[i.x]});
        }
      }
    }

    return dis[2 * n + 1];
  }

public:
  /**
   * 计算最小交换次数
   * @param firstRow int整型vector 第一行的身高数据
   * @param secondRow int整型vector 第二行的身高数据
   * @return int整型
   */
  int arrange(vector<int> &firstRow, vector<int> &secondRow) {
    int ans = solve(firstRow, secondRow);
    return ans == INF ? -1 : ans;
  }
};

动态规划的参考实现如下：

class Solution {
#define all(x) (x).begin(), (x).end()

  const int INF = 0x3f3f3f3f;

  template <typename T> inline bool chkmin(T &a, const T &b) {
    if (a < b) {
      return false;
    }
    a = b;
    return true;
  }

  int solve(const vector<int> &a, const vector<int> &b) {
    assert(a.size() == b.size());
    int n = a.size();

    vector<vector<int>> dp(n, vector<int>(2, INF));

    dp[0][0] = 0, dp[0][1] = 1;

    for (int i = 1; i < n; i++) {
      if (a[i - 1] > a[i] && b[i - 1] < b[i]) {
        chkmin(dp[i][0], dp[i - 1][0]);
      }

      if (a[i - 1] > b[i] && b[i - 1] < a[i]) {
        chkmin(dp[i][1], dp[i - 1][0] + 1);
      }

      if (a[i - 1] < a[i] && b[i - 1] > b[i]) {
        chkmin(dp[i][1], dp[i - 1][1] + 1);
      }

      if (a[i - 1] < b[i] && b[i - 1] > a[i]) {
        chkmin(dp[i][0], dp[i - 1][1]);
      }
    }

    return *min_element(all(dp.back()));
  }

public:
  /**
   * 计算最小交换次数
   * @param firstRow int整型vector 第一行的身高数据
   * @param secondRow int整型vector 第二行的身高数据
   * @return int整型
   */
  int arrange(vector<int> &firstRow, vector<int> &secondRow) {
    int ans = solve(firstRow, secondRow);
    return ans == INF ? -1 : ans;
  }
};