Đếm chuột túi

Submit solution
Points: 2 (partial)
Time limit: 1.0s
Python 3 3.0s
Memory limit: 250M
Python 3 98M
Author:
lqtuantk19
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

Có \(n\) con chuột túi và như chúng ta đã biết mỗi một con chuột túi đều có 1 cái túi. Ngoài túi ra mỗi con còn có một kích cỡ nhất định. Con chuột túi A có thể chui vào túi của con chuột B nếu kích thước của con chuột túi B lớn hơn ít nhất 2 lần so với con chuột A. Khi một con chuột đã trong túi của con chuột túi khác thì bạn sẽ không thể nhìn thấy chúng. Biết rằng mỗi con chuột túi chỉ cho tối đa một con khác chui vào và con chuột túi nào đang chứa con khác trong túi của mình thì nó không thể nhảy vào túi của con chuột túi khác. Nhiệm vụ của bạn là tìm cách tối ưu nhất để dấu các con chuột túi đi sao cho số lượng các con chuột có thể nhìn thấy là ít nhất.

Input

  • Dòng đầu tiên chứa số nguyên \(n\) là số con chuột túi (\(1 <= n <= 500005\))
  • \(n\) dòng tiếp theo mỗi dòng chứa một số nguyên \(a[i]\) là kích thước của con chuột túi thứ \(i\) (1 <= \(a[i]\) <= 100000)

Output

  • In ra một dòng duy nhất là số con chuột túi còn có thể nhìn thấy được.

Example

Input

8
9
1
6
2
6
5
8
3

Output

5

Giải thích Có thể cho con chuột kích thước 1 chui vào túi con chuột 5, con kích thước 2 chui vào con kích thước 6 và con kích thước 3 chui vào con có kích thước 9. Vậy có 3 con bị dấu đi và bây giờ bạn chỉ còn nhìn thấy được 5 con chuột.

Comments


  • 0
    NguyễnTườngHuy_CNTT1_K64  commented on May 23, 2024, 11:03 a.m.

    ll n ; cin >> n ;

    ll a[n] ; F1 ( 0 , n  ) cin >> a[i] ;

sort ( a , a + n ) ;

ll ans = n , i = 0 , j = n/2 ;

while ( i < n/2  && j < n ) {
    if ( a[i] * 2 <= a[j] ) {
        ans-- ;
        i++ ;
        j++ ;
    }
    else {
        j++ ;   
    }
}

cout << ans ;
return 0 ;

  • 0
    NguyenDongThinh_CNTT4_K61  commented on Nov. 2, 2021, 2:17 a.m.

    mng cho mình xin gợi ý được k ạ :<