ARC073E Ball Coloring

考虑有两种情况:

  • 全局最大值与全局最小值不在一边

这种情况比较简单,只要贪心的把一组中较大的放在最大值在的那边,把较小的放最小值那边就行了。

  • 全局最大值与全局最小值在一边

先将每组中较小的和较大的分开成两组

按较小的那个为关键字升序排,然后枚举交换。

这样子的话只要另一边的极差最小就是最优解,交换的话,不会使得最小值更小,如果将最大值交换了的话就不可能获得最优解,所以不用考虑这种情况。

#include <iostream>
#include <cstdio>
#include <algorithm>

typedef long long LL;

const int MAXN = 2e5;
const LL INF = 0x3f3f3f3f;

int n;
int mins[MAXN | 1], maxs[MAXN | 1];
LL ans;

struct Num {
  int a, b;
  Num() {}
  friend bool operator < (const Num &x, const Num &y) {
    return x.a < y.a;
  }
} p[MAXN | 1];

inline int read() {
  register int x = 0;
  register char ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x;
}

int main() {
  n = read();
  int min = 0, max = INF;
  int bmax = -1, rmax = -1;
  int bmin = INF, rmin = INF;
  for (int i = 1; i <= n; ++i) {
    p[i].a = read();
    p[i].b = read();
    if (p[i].a > p[i].b) std::swap(p[i].a, p[i].b);
    bmax = std::max(bmax, p[i].b);
    bmin = std::min(bmin, p[i].b);
    rmax = std::max(rmax, p[i].a);
    rmin = std::min(rmin, p[i].a);
  }
  LL ans2 = INF;
  std::sort(p + 1, p + 1 + n);
  ans = 1LL * (bmax - bmin) * (rmax - rmin);
  bmin = rmin;
  maxs[1] = mins[1] = p[1].b;
  for (int i = 2; i <= n; ++i) {
    maxs[i] = std::max(maxs[i - 1], p[i].b);
    mins[i] = std::min(mins[i - 1], p[i].b);
    if (i != n) ans2 = std::min(ans2, 1LL * std::max(maxs[i], p[n].a) - std::min(mins[i], p[i + 1].a));
  }
  printf("%d\n", std::min(ans, ans2 * (bmax - bmin)));
  return 0;
}
最后修改:2019 年 08 月 16 日 10 : 51 AM

发表评论