Link Sub: http://vn.spoj.com/problems/C11PAIRS/Người Gửi: Dương Lee
- Problem:
N người đang đứng xếp hàng chờ mua vé vào buổi hòa nhạc. Mọi người đều phát chán khi phải chờ đợi, vì vậy họ nhìn quanh xem có ai quen hay không.
Hai người A và B đứng trong hàng có thể nhìn thấy nhau nếu:
Người A và người B đang đứng cạnh nhau.
Giữa người A và người B, không có ai cao hơn hẳn một trong hai người.
Hãy đếm xem có bao nhiêu cặp có thể nhìn thấy nhau trong hàng.
Input
Dòng đầu tiên chứa số nguyên dương N, là số người đang đứng trong hàng.Mỗi dòng trong N dòng tiếp theo chứa một số nguyên là chiều cao của một người tính bằng nanomet. (Tất cả mọi người đều thấp hơn 231 nanomet).
Output
Một số nguyên duy nhất là kết quả cần tìm.
1 ≤ N ≤ 5.105
Trong 1/3 số test 1 ≤ N ≤ 5000
Example:
Input
7
2
4
1
2
2
5
1
Output:
10
- Solution:
Các cặp có thể nhìn thấy nhau là (1, 2), (2, 3), (2, 4), (2, 5), (2, 6), (3, 4), (4, 5), (4, 6), (5, 6), (6, 7).
- Ý tưởng: Sử dụng stack để loại các cặp không thể nhìn thấy được.
Chú ý cách làm dưới đây chỉ 100/100 khi nộp C++ (gcc 6.3) [CPP]
+ Duyệt từng người một: {mỗi người có 3 thông tin: +chiều cao: height; +kiểm tra sau nó: check_behind (Sử dụng để kiểm tra xem có sau nó có con nào lớn hơn không?); +kiểm tra đoạn giốn nhau: the_same (Sử dụng để đếm xem sau nó có bao nhiêu con có cùng độ cao); }
+TH1: Stack rỗng: Cho người đó vào với (chiều cao, 0 có ai sau nó, 0 có con nào bằng với nó).
VD: test trên (i==1: h_i=2) push (2, 0, 0); stack []: {(2, 0, 0);}
+TH2: Stack không rỗng và hight_TOP < h_i: loại những con bé hơn trong stack và count++; (Vì đã gặp con cao hơn thì các con sau sẽ không thể nhìn thấy con trước đó và hai con liên tiếp sẽ nhìn thấy nhau.)
VD: test trên (i==2: h_i=4) height_TOP = 2 < 4; ->pop() ->stack rỗng. -> push (4, 0, 0). cout++; stack []: {(4, 0, 0);}
+TH3: Stack không rỗng và hight_TOP > h_i: Các con sau vẫn có thể nhìn thấy nên push tiếp cùng với cập nhật chỉ số và count++ (hai con liên tiếp nhìn thấy nhau.)
VD: test trên (i==3: h_i=1) height_TOP= 4 > h_i; -> push (1, 1, 0) (chec_behind=1 vì sau con 1 có con 4 lớn hơn).
+TH4: Stack không rỗng và hight_TOP = h_i: trường hợp này khá đặc biệt vì các con bằng nhau liên tiếp vẫn có thể nhìn thấy nhau và vẫn có thể nhìn thấy con cao hơn sau nó.
VD: 4 2 2. thì (người thứ 3 vẫn nhìn được người 2 và người 1).
-> ta sẽ push vào chỉ số push (h, check_behind_TOP, the_same_TOP+1) (có nghĩa là: cho vào h, sau h có hay không có con cao hơn nó sẽ phụ thuộc vào con sau nó, sau nó có the_same+1 con cùng chiều cao với nó). Và coutn++ (liên tiếp nhìn thấy) và coun+=the_same_TOP (số con có cùng độ cao sau nó) và count++ (nếu sau nó có con cao hơn).
Cuối cùng thì in ra count. ^^ Xem hình để hiểu rõ hơn.
