题解：P3145 [USACO16OPEN] Splitting the Field G

· · 题解

前言:

本蒟蒻第一篇题解，存在问题的的地方还请各位多多包涵、指出。

核心思路

本题可以简化成在网格图中有 n 个点，让你圈出 2 个矩形，使得这 2 个矩形面积最小。

1.建立矩阵

题目中指出所有坐标都是正数，于是我们可以 (0,0) 为锚点，从远到近将所有的点排序。再从第一个点开始枚举，将点的序列分为前后两部分。

ans_{i} = S_{1, i} + S_{i + 1, n}

这样分可以将所有的点分成离锚点较近的和距离锚点较远的点，易证没有更优的分法。

2.求矩形面积

通过观察，我们可以发现矩形的长就是这些点中最大的 x 的值减去最小的 x 的值，宽是这些点中最大的 y 的值减去最小的 y 的值。

那我们的问题可以转化成区间内求最值。

数据范围是 1 \le n \le 50000 。

我们要枚举每一个点，找到每一个点的最大和最小的 x 和 y 的值，所以需要对查找操作进行优化。这里推荐使用 RMQ 。不懂戳这儿 RMQ 简单介绍。

注意事项:

  1. 我们应该将 x,y 分别排序，取最小值(只对 x 排序 80 分)。
  2. 不开 long long 见祖宗。
  3. RMQ 要设置初始值。
  4. 求出 ans 后要用整个矩形的面积减去 ans。

代码如下:

#include <bits/stdc++.h>
#define int long long
using namespace std;
/*
fx[i][j][0] 代表 i - j 区间内 x 的最小值
fx[i][j][1] 代表 i - j 区间内 x 的最大值
fy[i][j][0] 代表 i - j 区间内 y 的最小值
fy[i][j][1] 代表 i - j 区间内 y 的最大值
*/
int n, fx[50001][31][2], fy[50001][30][2], ans = 1e20, t, lx, ly, rx, ry;
struct cow{  //牛的位置
    int x, y;
}a[50001];
bool cmp1(cow a, cow b){  // 以 x 的远近排序
    return a.x < b.x;
}
bool cmp2(cow a, cow b){  // 以 y 的远近排序
    return a.y < b.y;
}
inline int read(){  // 读入优化
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0' || ch>'9'){ if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0' && ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x*f;
}
void rmq(){
    // 初始化
    for (int i = 0; i <= n; i++){
        for (int j = 0; j <= 30; j++){
            fx[i][j][0] = fy[i][j][0] = 1e20;
        }
    }
    for (int i = 1; i <= n; i++) fx[i][0][0] = fx[i][0][1] = a[i].x, fy[i][0][0] = fy[i][0][1] = a[i].y;

    for (int j = 1; j <= 30; j++){
        for (int i = 1; i + (1 << j) - 1 <= n; i++){
            fx[i][j][0] = min(fx[i][j - 1][0], fx[i + (1 << j - 1)][j - 1][0]);
            fx[i][j][1] = max(fx[i][j - 1][1], fx[i + (1 << j - 1)][j - 1][1]);
            fy[i][j][0] = min(fy[i][j - 1][0], fy[i + (1 << j - 1)][j - 1][0]);
            fy[i][j][1] = max(fy[i][j - 1][1], fy[i + (1 << j - 1)][j - 1][1]);
        }
    }
}
int find(int l, int r){  // l - r 区间内的面积
    t = log2(r - l + 1);
    lx = max(fx[l][t][1], fx[r - (1 << t) + 1][t][1]);
    rx = min(fx[l][t][0], fx[r - (1 << t) + 1][t][0]);
    ly = max(fy[l][t][1], fy[r - (1 << t) + 1][t][1]);
    ry = min(fy[l][t][0], fy[r - (1 << t) + 1][t][0]);
    return (lx - rx) * (ly - ry);
}
signed main() {
    n = read();
    for (int i = 1; i <= n; i++) a[i].x = read(), a[i].y = read();
    // x 
    sort(a + 1, a + 1 + n, cmp1);
    rmq();
    for (int i = 1; i < n; i++){
        int k = find(1, i), q = find(i + 1, n);
        ans = min(ans, k + q);
    }
    // y
    sort(a + 1, a + 1 + n, cmp2);
    rmq();
    for (int i = 1; i < n; i++){
        int k = find(1, i), q = find(i + 1, n);
        ans = min(ans, k + q);
    }

    cout << find(1, n) - ans;  // 输出答案，大面积减去小面积
    return 0;
}