首页 > ACM题库 > HDU-杭电 > HDU 3890-Apparent Magnitude-排序-[解题报告]HOJ
2015
04-13

HDU 3890-Apparent Magnitude-排序-[解题报告]HOJ

Apparent Magnitude

问题描述 :

Every time when I gazing at the dazzling night sky, I wonder that how many stars are there and how bright they are …
Statistical Problems

From Wikipedia, I know that we can use a metric called apparent magnitude (apmag) to describe the brightness of a star. The apparent magnitude of a celestial body is a measure of its brightness as seen by an observer on Earth, normalized to the value it would have in the absence of the atmosphere. The brighter the object appears, the lower the value of its magnitude would be.
In this problem, can you help me to count the stars and their average apmag in the sky?

输入:

There are several cases in the input, each case begin with two positive integer N (N<=60,000) and M (M<=20,000) giving the number of stars and queries. The following N lines give the 2D- coordinate (-10^8 < x, y < 10^8, integer) and the apmag (-40.00 < apmag < 40.00, a float number of two decimal places) of each star. After that, each of the following M lines contains four integers: -10^8 < lowX, lowY, upX, upY < 10^8, representing the lower-left and upper-right coordinates of a rectangle.

输出:

There are several cases in the input, each case begin with two positive integer N (N<=60,000) and M (M<=20,000) giving the number of stars and queries. The following N lines give the 2D- coordinate (-10^8 < x, y < 10^8, integer) and the apmag (-40.00 < apmag < 40.00, a float number of two decimal places) of each star. After that, each of the following M lines contains four integers: -10^8 < lowX, lowY, upX, upY < 10^8, representing the lower-left and upper-right coordinates of a rectangle.

样例输入:

4 2
1 1 1.24
2 2 4.56
3 3 7.89
4 4 3.21
1 1 2 2
5 6 7 8

样例输出:

5.80/2
0.00/0

题意:一个二维平面上有N个点,每个点都对应一个实数。有M次查询,每次查询一个矩形区域内的点的数量以及点所对应的实数之和。N<=60000,M<=20000。

解法:数据量很大,一定要把每次查询操作时间复杂度压缩到O(logn)以内,否则肯定会超时。开始想用二维线段树,或者对一维哈希,另一维暴力。但是点的数量太多,分布可能非常离散,二维线段树或者暴力哈希什么的肯定都是行不通的。那如何解呢?假设某次查询范围是 lx,ly,ux,uy (lx<=ux, ly<=uy)。如果我们统计出y范围为ly-uy,x范围为ux以下(包括ux)的数据d1
以及 y范围同上,x范围为lx以下(不包括lx)的数据d2。那么查询的结果就是 d1-d2。查询y的一段区间我们可以使用树状数组,但是x轴不好解决,假设我们每次查询都先把lx以下的点加入树状数组,然后再把ux以下的点加入树状数组,那么时间复杂度非常高。好在我们可以使用离线查询,先输入所有的查询。然后对查询的lx和ux排序,这样可以发现只要把点入两次树状数组就能完成所有的查询。

注意:输出结果时加上eps,否则可能会出现-0.00的结果。

#include <iostream>
#include <algorithm>
using namespace std;

const double eps = 1e-8;
const int maxn = 60005;
const int maxm = 20005;

struct Point {
    int x, y;
    double mag;
    bool operator < (const Point &oth) const {
        return x < oth.x;
    }
} pt[maxn];
struct Query {
    int lx, ly, ux, uy;
    int id, sc;
    double mc;
} qu[maxm];
bool lcmp(const Query &q1, const Query &q2) {
    return q1.lx < q2.lx;
}
bool ucmp(const Query &q1, const Query &q2) {
    return q1.ux < q2.ux;
}
bool idcmp(const Query &q1, const Query &q2) {
    return q1.id < q2.id;
}

int yhash[maxn+maxm+maxm], sz;
int n, m;
int cntC[maxn+maxm+maxm];
double magC[maxn+maxm+maxm];

int Find(int y) {
    int l = 0, r = sz - 1, m;
    while (l < r) {
        m = (l + r) >> 1;
        if (yhash[m] > y)
            r = m - 1;
        else if (yhash[m] < y)
            l = m + 1;
        else
            return m;
    }
    return l;
}

template<class T>
void Modify(int pos, const T &num, T C[]) {
    for ( ; pos <= sz; pos += (pos & (-pos))) {
        C[pos] += num;
    }
}
template<class T>
T GetSum(int pos, const T C[]) {
    T res = 0;
    for ( ; pos > 0; pos -= (pos & (-pos))) {
        res += C[pos];
    }
    return res;
}

int main() {
    int i, j, id, id1, id2;

    while(scanf("%d %d", &n, &m) != EOF) {
        sz = 0;
        for (i = 0; i < n; i++) {
            scanf("%d %d %lf", &pt[i].x, &pt[i].y, &pt[i].mag);
            yhash[sz++] = pt[i].y;
        }
        for (i = 0; i < m; i++) {
            scanf("%d %d %d %d", &qu[i].lx, &qu[i].ly, &qu[i].ux, &qu[i].uy);
            qu[i].id = i; qu[i].sc = 0; qu[i].mc = 0.0;
            yhash[sz++] = qu[i].ly;
            yhash[sz++] = qu[i].uy;
        }
        sort(yhash, yhash + sz);
        j = 1;
        for (i = 1; i < sz; i++) {
            if (yhash[i] != yhash[i-1])
                yhash[j++] = yhash[i];
        }
        sz = j;

        sort(pt, pt + n);
        sort(qu, qu + m, ucmp);
        memset(cntC + 1, 0, sz * 4);
        memset(magC + 1, 0, sz * 8);
        for (i = j = 0; i < m; i++) {
            while (j < n && pt[j].x <= qu[i].ux) {
                id = Find(pt[j].y);
                Modify(id + 1, 1, cntC);
                Modify(id + 1, pt[j].mag, magC);
                j++;
            }
            id1 = Find(qu[i].ly);
            id2 = Find(qu[i].uy);

            qu[i].sc += GetSum(id2 + 1, cntC) - GetSum(id1, cntC);
            qu[i].mc += GetSum(id2 + 1, magC) - GetSum(id1, magC);
        }
        sort(qu, qu + m, lcmp);
        memset(cntC + 1, 0, sz * 4);
        memset(magC + 1, 0, sz * 8);
        for (i = j = 0; i < m; i++) {
            while (j < n && pt[j].x < qu[i].lx) {
                id = Find(pt[j].y);
                Modify(id + 1, 1, cntC);
                Modify(id + 1, pt[j].mag, magC);
                j++;
            }
            id1 = Find(qu[i].ly);
            id2 = Find(qu[i].uy);

            qu[i].sc -= GetSum(id2 + 1, cntC) - GetSum(id1, cntC);
            qu[i].mc -= GetSum(id2 + 1, magC) - GetSum(id1, magC);
        }
        sort(qu, qu + m, idcmp);
        for (i = 0; i < m; i++) {
            printf("%.2lf/%d\n", qu[i].mc + eps, qu[i].sc);
        }
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/racebug2010/article/details/6654281


  1. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。