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

USACO(W) (滑稽

题目解析

题目在线详情(提交地址):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;
}