codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1007A.md (1837B)


      1 Source: https://codeforces.com/problemset/problem/1007/A
      2 
      3 A. Reorder the Array
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 You are given an array of integers. Vasya can permute (change order) its integers. He wants to do it so that as many as possible integers will become on a place where a smaller integer used to stand. Help Vasya find the maximal number of such integers.
     22 
     23 For instance, if we are given an array $[10, 20, 30, 40]$, we can permute it so that it becomes $[20, 40, 10, 30]$. Then on the first and the second positions the integers became larger ($20 \gt 10$, $40 \gt 20$) and did not on the third and the fourth, so for this permutation, the number that Vasya wants to maximize equals $2$. Read the note for the first example, there is one more demonstrative test case.
     24 
     25 Help Vasya to permute integers in such way that the number of positions in a new array, where integers are greater than in the original one, is maximal.
     26 
     27 Input
     28 
     29 The first line contains a single integer $n$ ($1 \leq n \leq 10^5$) — the length of the array.
     30 
     31 The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^9$) — the elements of the array.
     32 
     33 Output
     34 
     35 Print a single integer — the maximal number of the array's elements which after a permutation will stand on the position where a smaller element stood in the initial array.
     36 
     37 Examples
     38 
     39 Input
     40 
     41 ```
     42 7  
     43 10 1 1 1 5 5 3
     44 ```
     45 
     46 Output
     47 
     48 ```
     49 4
     50 ```
     51 
     52 Input
     53 
     54 ```
     55 5  
     56 1 1 1 1 1
     57 ```
     58 
     59 Output
     60 
     61 ```
     62 0
     63 ```
     64 
     65 Note
     66 
     67 In the first sample, one of the best permutations is $[1, 5, 5, 3, 10, 1, 1]$. On the positions from second to fifth the elements became larger, so the answer for this permutation is 4.
     68 
     69 In the second sample, there is no way to increase any element with a permutation, so the answer is 0.