221

221

题目链接如下：

Online Judge

首先，我的代码虽然AC了，但是是有问题的，uva的测试数据太水了所以侥幸通过而已。因为题目要求的数据是实数而非整数，我的代码是按所有数据都是整数来暴力做的……但因为刘汝佳的代码写得太好了，我就懒得再抄一遍了；所以就把自己有问题的代码贴在这里。

正确的解法在这里（也是刘汝佳的思路）：UVA ~ 221 ~ Urban Elevations （离散化）-CSDN博客

#include <cstdio>
#include <vector>
#include <algorithm>
#include <set>
// #define debug
const int maxx = 1000000;struct building{int x, y, width, depth, height, number;building(){}building(int _x, int _y, int _width, int _depth, int _height): x(_x), y(_y), width(_width), depth(_depth), height(_height){}
};
int n, x, y, width, depth, height, kase = 0;
std::vector<building> vec;
std::vector<int> ans[maxx];bool cmp1(const int &a, const int &b){return vec[a - 1].y < vec[b - 1].y;
}bool cmp2(const int &a, const int &b){return vec[a - 1].x != vec[b - 1].x ? vec[a - 1].x < vec[b - 1].x : (vec[a - 1].y < vec[b - 1].y);
}int main(){#ifdef debugfreopen("1.txt", "r", stdin);freopen("2.txt", "w", stdout);#endifwhile(scanf("%d", &n) == 1 && n){printf("%s", kase ? "\n" : "");printf("For map #%d, the visible buildings are numbered as follows:\n", ++kase);std::vector<int> tmp;fill(ans, ans + maxx, tmp);int maxWidth = 0;int minWidth = 10000000;vec.clear();for(int i = 1; i <= n; ++i){scanf("%d %d %d %d %d", &x, &y, &width, &depth, &height);vec.push_back(building(x, y, width, depth, height));vec.back().number = i;maxWidth = std::max(maxWidth, x + width);minWidth = std::min(minWidth, x);for(int j = x; j < x + width; ++j){ans[j].push_back(i);}}for(int i = minWidth; i < maxWidth; ++i){sort(ans[i].begin(), ans[i].end(), cmp1);int height = 0;for(int j = 0; j < ans[i].size(); ++j){if(vec[ans[i][j] - 1].height > height){height = vec[ans[i][j] - 1].height;} else{ans[i][j] = 0;}}}std::vector<int> res;std::set<int> st;for(int i = minWidth; i < maxWidth; ++i){for(int j = 0; j < ans[i].size(); ++j){if(ans[i][j] && st.find(ans[i][j]) == st.end()){res.push_back(ans[i][j]);st.insert(ans[i][j]);}}}sort(res.begin(), res.end(), cmp2);for(int i = 0; i < res.size(); ++i){printf("%d%s", res[i], i == res.size() - 1 ? "\n" : " ");}}#ifdef debugfclose(stdin);fclose(stdout);#endifreturn 0;
}