首页 > ACM题库 > HDU-杭电 > HDU 3490-Manhattan Distance[解题报告]HOJ
2014
04-04

HDU 3490-Manhattan Distance[解题报告]HOJ

Manhattan Distance

问题描述 :

The kingdom of Henryy is the most civilized country in the world. Meanwhile, the capital city H is as well the most beautiful city on the earth. Currently, the city is to build up database to maintain the statistics of the buildings in the city.
You are a little P in the company that takes this project. Your task is to calculate the maximum distance between two buildings in the city.
The Manhattan Distance is defined as: for two points P1(x1, y1) and P2(x2, y2) on a two dimension Cartesian plane, the Manhattan Distance D(P1, P2) = |x1-x2|+|y1-y2|.
Your database should support this query: after updating a data that a building has built or demolished, it should return the maximum distance between existed buildings:

Necklace

N is the current number of buildings, and Pi is the coordinates of the ith building.

输入:

The first line contains an integer T (T<=10), indicating the number of the test cases.
For each test case, the first line contains an integer M (M<=100000), the number of records of the changes of buildings.
Then M lines followed, each line starting with a positive integer: 1 for building that has built, and 2 for demolished. A string with less than 9 characters follows, indicating the name of the building. If this building is just built, two integers of the coordinates of this building are given afterwards.
Notice that no two buildings share the same name, even when one of these buildings has been demolished, but might share the same coordinates. It is also guaranteed that the building exists when a demolishing record is given.
A blank line is followed after each test case.

输出:

The first line contains an integer T (T<=10), indicating the number of the test cases.
For each test case, the first line contains an integer M (M<=100000), the number of records of the changes of buildings.
Then M lines followed, each line starting with a positive integer: 1 for building that has built, and 2 for demolished. A string with less than 9 characters follows, indicating the name of the building. If this building is just built, two integers of the coordinates of this building are given afterwards.
Notice that no two buildings share the same name, even when one of these buildings has been demolished, but might share the same coordinates. It is also guaranteed that the building exists when a demolishing record is given.
A blank line is followed after each test case.

样例输入:

1
8
1 mgj -2 1
2 mgj
1 kmoaktmr 4 -4
1 mauxizu 3 -2
2 kmoaktmr
1 md -1 4
2 md
1 umos -5 0

样例输出:

0
-1
0
3
0
10
0
10


这题其实很简单的,被我想复杂了 =       =…

其实我想到 x – y 和 x + y 的,但是我以为每次要以一个点为中心进行处理,然后就没有做出这题,后来隐隐约约听到 yzc 说到 用 map 来做,我就猜出其实不需要以每个点为中心进行处理了,因为这两个模式中,结果大的那个才是有效值,所以这样做是正确的。唉,居然被卡在这种地方。后来 yzc 说了这题目很常见,第一次见的时候是三维的,就是 4 种模式。交谈一番后,才知道为什么他们总拿我们当小朋友了,很多东西其实他们都是懂的,但就是不讲的,只有到你到了他们觉得可以讲的时候才会讲。今天还碰到了 dk ,虽然没有直接学到什么东西,但是感觉收获还是有的。

C++语言: hdu 3490
01 #include <cstdio>
02 #include <cstring>
03 #include <string>
04 #include <map>
05 using namespace std;
06
07 map<string, pair<int, int> > ms;
08 map<int, int> s1, s2;
09
10 int n;
11
12 inline int calc(map<int, int>& s) {
13     map<int, int>::iterator ib = s.begin(), ie = s.end();
14     return (ie)->first - ib->first;
15 }
16
17 inline void erase(map<int, int> &s, int x) {
18     if (s[x] == 0)
19         s.erase(x);
20 }
21
22 int main() {
23 #ifndef ONLINE_JUDGE
24     freopen(“in.txt”, “r”, stdin);
25     freopen(“out.txt”, “w”, stdout);
26 #endif
27     int test;
28     scanf(“%d”, &test);
29     for (int cas = 1; cas <= test; ++cas) {
30         ms.clear(); s1.clear(); s2.clear();
31         scanf(“%d”, &n);
32         for (int i = 0; i < n; ++i) {
33             int opt; char buf[100];
34             scanf(“%d%s”, &opt, buf);
35             if (opt == 1) {
36                 int x, y;
37                 scanf(“%d%d”, &x, &y);
38                 ms[buf] = pair<int, int>(x, y);
39                 s1[x - y]++; s2[x + y]++;
40             } else {
41                 map<string, pair<int, int> >::iterator it = ms.find(buf);
42                 erase(s1, it->second.first - it->second.second);
43                 erase(s2, it->second.first + it->second.second);
44                 ms.erase(it);
45             }
46             if (ms.size() == 0)
47                 puts(“-1″);
48             else
49                 printf(“%d\n, max(calc(s1), calc(s2)));
50         }
51         putchar(‘\n’);
52     }
53     return 0;
54 }
参考:http://xpycc.blog.163.com/blog/static/502669022010719103224232/


  1. 因为是要把从字符串s的start位到当前位在hash中重置,修改提交后能accept,但是不修改居然也能accept