solution

讨论

「Usaco2016 Feb」Load balancing S

solution

这道题有两个版本，还有一个版本是 , 需要用到高级数据结构

本题 , 故可以考虑的做法，但是这里的坐标很大，因此我们可以离散化坐标（离散化就是把坐标的具体大小变成相对大小，这样坐标的范围也就在内了）之后采用二维前缀和优化，最后直接枚举分界点即可。

学有余力的同学可以挑战一下 Load balancing G

参考代码：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#define MAXN 100005


#define LL long long


#define INF 2147483647


#define MOD 1000000007


using namespace std;
const int L = 1005;
struct node {
    LL int s, num;
};
node zx[L], zy[L];
bool cmp(const node &b, const node &c) { return b.s < c.s; }
LL int n, x[L], y[L], ans = INF, sum[L][L];
int main() {
    scanf("%lld", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%lld%lld", &zx[i].s, &zy[i].s);
        zx[i].num = i;
        zy[i].num = i;
    }
    sort(zx + 1, zx + n + 1, cmp);
    sort(zy + 1, zy + n + 1, cmp);
    for (int i = 1; i <= n; i++) {
        x[zx[i].num] = i;
        y[zy[i].num] = i;
    }  //离散化
    for (int i = 1; i <= n; i++) sum[x[i]][y[i]]++;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];  //预处理部分
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            ans = min(ans, max(max(sum[i][j], sum[i][n] - sum[i][j]),
                               max(sum[n][j] - sum[i][j],
                                   sum[n][n] - sum[n][j] - sum[i][n] + sum[i][j])));  //四个象限
    printf("%lld", ans);
    return 0;
}

Zhang_Ruchen

2023-07-08 10:09:03

数轴上的离散化：我们记录一个结构体{data, id}，按顺序读入 data ，然后将 id 赋值为读入时的编号。然后按 {data} 从小到大排列，其中 id 跟随着整个结构体排列，也就是说按 {data} 排列完之后，{id} 是无序的。此时我们再依次取出结构体里面的数据，用新的一个数组 {a} 来存放离散化后的数据。

按照一维的思路来讲代码。排序前 zx[i].num = i，先记录一个 i，按 s 排序完之后，存新的数组 x[zx[i].num] = i。都有个 zx[i].num = i !!

那么二维平面同理，把 x, y 分开离散化，再用一个数组存下来。注意这两个数组跟 dx 和 dy 是一样的，即一个 i，必定对应的一个合法的点坐标 {x, y}

四个象限的推导比较简单，参考矩形面积即可。

共 1 条回复