HDU - 3634 离散化

题意：

思路：

代码：

#include <cstdio>#include <cstring>#include <algorithm>using namespace std;typedef long long ll;const int N = 50;int y[N], x[N], n, m;ll val[N][N];struct Rect {    int x1, y1, x2, y2, v;    bool Operator < (const Rect &r) const {        return v < r.v;    }} r[N];int fid(int a[], int k) {    return lower_bound(a, a + m, k) - a;}int main() {    int T, x1, y1, x2, y2, cas = 0;    scanf("%d", &T);    while(T--) {        scanf("%d", &n);        for(int i = m = 0; i < n; ++i, m += 2) {            scanf("%d%d%d%d%d", &r[i].x1, &r[i].y1, &r[i].x2, &r[i].y2, &r[i].v);            x[m] = r[i].x1, x[m + 1] = r[i].x2;            y[m] = r[i].y1, y[m + 1] = r[i].y2;        }        sort(r, r + n);        sort(x, x + m);        sort(y, y + m);        memset(val, 0, sizeof(val));        for(int i = 0; i < n; ++i) {            x1 = fid(x, r[i].x1), x2 = fid(x, r[i].x2);  //获得x离散化后的坐标            y1 = fid(y, r[i].y1), y2 = fid(y, r[i].y2);  //获得y离散化后的坐标            for(int j = x1; j < x2; ++j)                for(int k = y1; k < y2; ++k)  //  直接暴力更新离散化后的方格                    val[j][k] = r[i].v;        }        ll ans = 0;        for(int i = 0; i < m - 1; ++i)            for(int j = 0; j < m - 1; ++j)                ans += val[i][j] * (x[i + 1] - x[i]) * (y[j + 1] - y[j]);        PRintf("Case %d: %I64d/n", ++cas, ans);    }    return 0;}