Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

BCTEST17 - Xếp hàng 2

Lại nhắc đến Chí Phèo khi xếp hàng đi mua Iphone 4S, trong lúc chờ đợi, anh lại nghĩ ra một bài toán để thử tài các bạn sinh viên PTIT.

Có tất cả N người xếp hàng.  Hai người AB sẽ nhìn thấy nhau nếu giữa 2 người không có người nào cao hơn người A hoặc B. Bạn hãy xác định số cặp người có thể nhìn thấy nhau.

Dữ liệu:

Dòng 1: Một số nguyên duy nhất N (1≤N≤500 000) là số người đứng xếp hàng.

Dòng 2..N+1: Mỗi dòng là chiều cao của một người đứng xếp hàng theo thứ tự từ đầu hàng tới cuối hàng. Chiều cao một người không quá 231.

Kết quả:

Một số nguyên duy nhất là số cặp người xếp hàng có thể nhìn thấy nhau.

Ví dụ:

INPUT

OUTPUT

7

2

4

1

2

2

5

1

10

Giải thích:

-          Người ở vị trí thứ 1 có thể nhìn thấy người ở vị trí thứ 2

-          Người ở vị trí thứ 2 có thể nhìn thấy người ở vị trí thứ 1,3,4,5,6

-          Người ở vị trí thứ 3 có thể nhìn thấy người ở vị trí thứ 2,4

-          Người ở vị trí thứ 4 có thể nhìn thấy người ở vị trí thứ 2,3,5,6

-          Người ở vị trí thứ 5 có thể nhìn thấy người ở vị trí thứ 2,4,6.

-          Người ở vị trí thứ 6 có thể nhìn thấy người ở vị trí thứ 2,4,5,7.

-          Người ở vị trí thứ 7 có thể nhìn thấy người ở vị trí thứ 6

=>  Có tất cả 10 cặp người có thể nhìn thấy nhau.

 


ID RESULT TIME
code...



Được gửi lên bởi:Admin
Ngày:2011-11-17
Thời gian chạy:0.200s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL6 PERL PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

hide comments
2017-04-09 17:35:35
sao dùng 2 vòng for lại báo sai v mng ???
#include<iostream>

using namespace std ;

int a[500005] ;

main(){
int n , count = 0 ;
cin >> n ;

for( int i = 0 ; i < n ; i++ ) cin >> a[i] ;

for( int i = 0 ; i < n - 1 ; i++)
for( int j = i + 1 ; j < n ; j++ )
if( a[j] <= a[i] ) count++ ;
else{
count++ ;
break ;
}

cout << count ;
}
2015-08-12 17:28:29
bài này 1 nhìn thấy 6 mà.....
2014-10-18 18:02:57 Cường D14AT1
KHS chỉ được 50đ -__- nhất định ko tìm ra được lỗi sai chỗ nào, thánh nào chịu giúp k, please ...
2014-08-27 13:50:33 Black Hole
dùng stack là hợp lý rồi :v
2014-04-11 12:21:47 Hướng Thái Dương
bài này IT khó ac :))
2013-07-14 01:29:07 kimi
bài này mình nghĩ dùng IT.nhưng vẫn chưa làm được
2012-11-16 05:46:45 Vương Sỹ Huấn DH BK TP HCM
The lam nhu the nao
2012-11-03 16:48:36 Tobi
Ý tưởng là sử dụng stack<>. Mỗi lần nhập vào là xử lý luôn rồi đẩy vào stack
2012-11-03 15:17:27 Trần Vãn Dương D10CN2
May xep oi y tuong la j the
2012-11-03 14:15:34 Tobi
Ai có ý tưởng cho bài này không ạ em chỉ làm được O(n^2) thôi
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.