Load Balancing 解题报告（USACO 2016 February Contest, Silver. Problem 2. 排序 树状数组 离散化）

2018-04-13

USACO(W) （滑稽

本文迁移自老博客，原始链接为 https://lookas2001.com/load-balancing-%e8%a7%a3%e9%a2%98%e6%8a%a5%e5%91%8a/

题目解析

题目在线详情（提交地址）：http://www.usaco.org/index.php?page=viewproblem2&cpid=619

题目意思其实很简单，给定一个二维矩阵（农场），其中放置着许多点（牛），求在一个恰当的地方切水平竖直两刀，使得所切的四个区域中点最多的那个区域中的点最少。（啥，还没看懂？回到题目详情继续啃英文）

算法设计

且不考虑什么 k-d tree 这种特别高级的算法，我们先想一想暴力怎么做？枚举每一个切割点（水平竖直切割线的交点）！但是，我们可以发现，由于x，y都特别大，这样会导致程序最后时间非常慢...

Wait！为啥点才1000多个？对，我们可以简单的在大脑中想，这么一个大矩阵，一大堆空间都是0，也就是说我们枚举了很多没用的位置点，我们可以对x，y单独（想一想为什么单独做是可以的）做一次离散化，这样可以迅速让枚举范围减小。离成功进了一步！

但是，依然很慢 O(n^3) ，原因其实蛮简单的，因为统计区域内的点非常的慢，每一次统计我们都统计了上次统计过的点。那为什么我们不想想办法解决这个问题呢？首先，我们可以让这些牛 有序 （其实这是我最开始的想法，比离散化的想法还要早一些），我们按行往下推进，然后我们对水平切割线的上下分别建立一个树状数组。（其实最开始我的想法是对每一行都建立一棵线段树的，但是发现其实没有必要每一行都建立一棵的），然后枚举每一个垂直切割线，这样我们的复杂度降低到了 O(n ^ 2 * logn)

实例代码

#include <cstdio>
#include <cstring>
#include <algorithm>

const int N = 1100;

int n;
struct cd {
    int x, y;
} c[N];

bool cmp(cd a, cd b) {
    if (a.x == b.x) return a.y < b.y;
    return a.x < b.x;
}

int *d[N];

bool cmp_d(int *a, int *b) {
    return *a < *b;
}

int t[N], b[N]; // 水平轴切开的上下两部分，top bottom

void change(int t[], int k, int x) {
    while (k <= n) {
        t[k] += x;
        k += k & (-k);
    }
}

int sum(int t[], int k) {
    int x = 0;
    while (k > 0) {
        x += t[k];
        k -= k & (-k);
    }
    return x;
}

int main() {
//  freopen("input.txt", "r", stdin);
    freopen("balancing.in", "r", stdin);
    freopen("balancing.out", "w", stdout);

    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d%d", &c[i].x, &c[i].y);

    // 对x进行排序，便于下方移动水平轴
    std::sort(c + 1, c + n + 1, cmp);
//  for (int i = 1; i <= n; i++) printf("%d %d\n", c[i].x, c[i].y); printf("\n");

    // 对y进行离散化，便于下方移动垂直轴
    for (int i = 1; i <= n; i++) d[i] = &c[i].y;
    std::sort(d + 1, d + n + 1, cmp_d);
    int last = 0, count = 0;
    for (int i = 1; i <= n; i++) {
        if (*d[i] != last) {
            count++;
            last = *d[i];
        }
        *d[i] = count;
    }
//  for (int i = 1; i <= n; i++) printf("%d %d\n", c[i].x, c[i].y); printf("\n");

    // 移动水平轴，并且枚举垂直轴
    memset(t, 0, sizeof t);
    memset(b, 0, sizeof b);
    for (int i = 1; i <= n; i++) change(b, c[i].y, 1); // 先填充水平轴下方的内容
    int ans = 0x7fffffff;
    int i = 1;
    while (i <= n) {
        int row = c[i].x;
        // 从水平轴下方删除，并且添加到水平轴上方
        while (i <= n && c[i].x == row) {
            change(t, c[i].y, 1);
            change(b, c[i].y, -1);
            i++;
        }

        for (int j = 1; j <= n; j++) {
            int tmp, stage_ans = 0;
            tmp = sum(t, j); // 上左
            if (tmp > stage_ans) stage_ans = tmp;
            tmp = sum(t, n) - tmp; // 上右
            if (tmp > stage_ans) stage_ans = tmp;
            tmp = sum(b, j); // 下左
            if (tmp > stage_ans) stage_ans = tmp;
            tmp = sum(b, n) - tmp; // 下右
            if (tmp > stage_ans) stage_ans = tmp;
            if (stage_ans < ans) ans = stage_ans;
        }
    }
    printf("%d", ans);

    return 0;
}