HDU - 3634离散化

题意：

给n个矩形，每个矩形都有自己的单位价值，矩形之间可能会有重叠部分，对于重叠部分任意选择属于哪个矩形，求能构成的最大的价值。

思路：

看题解时学到了一种优秀的离散化方法。 这里将x和y分别离散化，然后每个坐标都构成一个点，组成2*n * 2*n的小方格，因为n非常小，所以遍历到一个矩形的时候，先找到它x1,y1,x2,y2对应的离散化后的坐标，然后将这一区域内的所有小方格都更新成当前矩形的value，所以要按照value从小到大的顺序遍历，用大的替代小的。最后统计答案，就直接把所有小方格的价值和相加即可。

代码：

#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; }