CF1178H Sol

Z1qqurat · 2023-12-19 17:34:09 · 题解

update on 2024/1/2：更新了代码以及对 check 的方式的描述，主要问题就是只需要知道能换成的 at+b 最大值，不需要知道换成具体哪种票。感谢 @YukinoYukinoshita 指出了错误并给出 hack。hack 如下：

也可以结合这组数据食用：

CF 官解的网络流建模是不是错的啊……我自己写的那种常数大一点，点数有 \mathcal{O}(5n) 但是也能过。

首先这种最小化问题，如果不好直接求就考虑判定。二分一个结束时间 t，判断是否能在 t 内换完。容易证明一个结论：如果 t 是合法的，那么任何一种方案都可以转化为只有在时刻 0 和时刻 t 换。我们可以将股票的价格看作一个一次函数（不是严格意义上的），两条直线顶多只有一个交点，如果需要在交后换的话那么就在 t 换，否则在 0 换就可以了。

那么现在再来判定就很简单了，是一个标准的最小费用最大流问题。交换一次费用为 1，最终换出一个 (n,2n] 中的一个流量加 1。设点 i 表示股票 i，c_i=a_it+b_i，我们先不考虑时空复杂度，进行建模：

首先，源点 S 向 i\in[1,n] 连边，容量和费用分别为 (1,0)，表示初始情况下有一张邮票 i。
对于每个 i\in[1,n]，向每个 j 满足 j\in[1,2n],b_i\ge b_j 连边，容量和费用分别为 (+\infty,1)，表示在 0 时刻 i 可以换成 j。
对于每个 i\in[1,2n]，向每个 j 满足 j\in(n,2n],c_i\ge c_j 连边，容量和费用分别为 (+\infty,1)，表示在 t 时刻 i 可以换成 j。

那么最后如果该图的最大流为 n，那么其最小费用就是结束时间为 t 时的最少交换次数。先不看时间复杂度，单说空间复杂度，3,4 类边是 \mathcal{O}(n^2) 的，而本题空间极小，根本过不去。

发现如果我们把点按 b_i 从大到小排序，那么 3 中每个点连的是一段后缀，4 同理。这启发我们使用后缀优化建图，为了正确地分配费用，我采用了一种建虚点的方式，假如将点 1\sim 2n 按照 b_i 值从大到小排序后，点的编号序列为 2,1,4,6,5,3，那么建虚点如图：

其中边权表示的是费用，容量都是 +\infty 所以省略了。那么假如说点 2 要向后缀 6,5,3 连边，它直接向 v_4 连边就可以了。3 类边中对于每个点都要建虚点，所以虚点个数 2n。

对于 4 类边，由于只用向 j\in(n,2n] 连边，所以我们只需要新建 n 个虚点同样的方式做即可。每个点找到要找到第一个能连边的点编号，这可以二分，因为我们会将点按照 b_i 或者 c_i 排序。当然暴力 \mathcal{O}(n^2) 枚举也没有问题。费用流我们跑 EK 即可（不知道为什么 Dinic 就过不了），因为边数只有 \mathcal{O}(11n)（未计算反向边）级别，所以大概只要 \mathcal{O}(kn^2)，k 是一个很小的常数。

但是这仍然复杂度很高嘞，每次二分 check 都要跑一次，多了个 \log V。发现二分的时候其实只需要知道是否可行而不需要知道最小交换次数！考虑贪心来判断。

考虑对于每种 1\sim n 的票求出其在 0 时刻能换成的 at+b 最大的股票，这可以简单排序求，然后我们定义数组 c_i，如果 i\in[1,n] 那么表示 i 在 0 时刻能换成的 at+b 最大值，否则表示 a_it+b_i。那么我们将 [1,2n] 按照 c 倒序排序，直接判断每个前缀中是否都满足 \le n 的数不少于 >n 的数，类似于判断合法括号序的。原理手画一个数轴就能明白了，不再赘述。于是我们可以在 \mathcal{O}(n\log V) 时间内求出 t。最后已知 t 再跑一遍 EK 即可。

代码实现细节我觉得蛮多的……调了好久好久，多注意一下吧。

//Code by Shinobu Sengoku.
#include <bits/stdc++.h>
#define ALL(v) begin(v), end(v)
using i64 = int64_t;
using std::cin;
using std::cout;
constexpr int N = 1.11e5 + 5;

int n, n2, n3, tot = 1, ss, tt, maxflow;
std::array<int, N> a, b, x, y, cnt;
std::array<i64, N> c;
std::array<int, N * 3> to, head, nxt, limit, cost;

auto addedge(int u, int v, int f, int c) {
   to[++tot] = v, limit[tot] = f, cost[tot] = c, nxt[tot] = head[u], head[u] = tot;
   to[++tot] = u, limit[tot] = 0, cost[tot] = -c, nxt[tot] = head[v], head[v] = tot;
   return ;
}

auto check(int t) {
   std::fill(&cnt[1], &cnt[n2 + 1], 0);
   std::iota(&x[1], &x[n2 + 1], 1);
   for (auto i = 1; i <= n2; ++i)
    c[i] = (i64)a[i] * t + (i64)b[i];
   std::stable_sort(&x[1], &x[n2 + 1], [&](int p, int q) {
        return (b[p] == b[q] ? c[p] > c[q] : b[p] < b[q]); });

   auto cur = (i64)0;
   for (auto i = 1; i <= n2; ++i) {
    auto j = x[i];
    c[j] = (i64)a[j] * t + (i64)b[j];
    cur = std::max(cur, c[j]);
    if (j <= n) c[j] = cur;
   }

    std::iota(&y[1], &y[n2 + 1], 1);
   std::stable_sort(&y[1], &y[n2 + 1], [&](int p, int q) { 
        return (c[p] == c[q] ? p > q : c[p] < c[q]); });
    cur = 0;
   for (auto i = n2; i; --i) {
    cur += (y[i] <= n ? 1 : -1);
    if (cur < 0) return 0;
    }
    return 1;
}

namespace MCMF { // MinCost MaxFlow
std::array<bool, N> vis;
std::array<int, N> dis, flow, pre;
std::queue<int> q;

auto mincost(int s, int t) {
    auto ret = (i64)0;
    while (1) {
        std::fill(&dis[1], &dis[t + 1], 2e9), std::fill(&vis[1], &vis[t + 1], 0);
        while (!q.empty()) q.pop();
        dis[s] = 0, flow[s] = N, q.emplace(s), vis[s] = 1;
        while (!q.empty()) {
            auto u = q.front(); q.pop();
            vis[u] = 0;
            for (auto i = head[u]; i; i = nxt[i]) {
                auto v = to[i];
                if (dis[v] > dis[u] + cost[i] && limit[i]) {
                    pre[v] = i, dis[v] = dis[u] + cost[i];
                    flow[v] = std::min(flow[u], limit[i]);
                    if (!vis[v]) q.emplace(v), vis[v] = 1;
                }
            }
        }
        if (dis[t] == 2e9) return ret;
        ret += (i64)dis[t] * flow[t], maxflow += flow[t];
        for (auto u = t; u != s; u = to[pre[u] ^ 1])
            limit[pre[u]] -= flow[t], limit[pre[u] ^ 1] += flow[t];
    }
}
} // namespace MCMF

auto build(int t) {
    std::iota(&x[1], &x[n2 + 1], 1);
   std::sort(&x[1], &x[n2 + 1], [&](int p, int q) { 
        return (b[p] == b[q] ? p > q : b[p] > b[q]); });
   for (auto i = 1; i <= n2; ++i) {
      addedge(i + n2, x[i], N, 1);
      if (i < n2) addedge(i + n2, i + 1 + n2, N, 0);
   }

   for (auto i = 1; i <= n2; ++i)
      c[i] = (i64)a[i] * t + (i64)b[i];
   std::iota(&y[n + 1], &y[n2 + 1], n + 1);
   std::sort(&y[n + 1], &y[n2 + 1], [&](int p, int q) { 
        return (c[p] == c[q] ? p > q : c[p] > c[q]); });
   for (auto i = n + 1; i <= n2; ++i) {
      addedge(i + n3, y[i], N, 1);
      if (i < n2) addedge(i + n3, i + 1 + n3, N, 0);
   }

   ss = 5 * n + 1, tt = ss + 1;
   for (auto i = 1; i <= n; ++i) addedge(ss, i, 1, 0);
   for (auto i = n + 1; i <= n2; ++i) addedge(i, tt, 1, 0);
   for (auto i = 1; i <= n; ++i) {
      auto lt = 0, rt = n2 + 1;
      while (lt + 1 < rt) {
         auto mid = lt + rt >> 1;
         if (b[i] >= b[x[mid]]) rt = mid;
         else lt = mid;
      }
      if (rt >= 1 && rt <= n2) addedge(i, rt + n2, N, 0);
   }
   for (auto i = 1; i <= n2; ++i) {
      auto lt = n, rt = n2 + 1;
      while (lt + 1 < rt) {
         auto mid = lt + rt >> 1;
         if (c[i] >= c[y[mid]]) rt = mid;
         else lt = mid;
      }
      if (rt > n && rt <= n2) addedge(i, rt + n3, N, 0);
   }
   return;
}

auto main() -> int {
   std::ios::sync_with_stdio(false);
   cin.tie(nullptr), cout.tie(nullptr);

   cin >> n, n2 = n << 1, n3 = n * 3;
   for (auto i = 1; i <= n2; ++i) cin >> a[i] >> b[i];

   auto lt = -1, rt = (int)2e9 + 1;
   while (lt + 1 < rt) {
      auto mid = (lt - rt >> 1) + rt;
      if (check(mid)) rt = mid;
      else lt = mid;
   }

   if (rt == 2e9 + 1) cout << "-1\n";
   else {
      build(rt);
      cout << rt << ' ' << MCMF::mincost(ss, tt) << "\n";
   }
   return 0;
}