• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# [USACO][Analysis][2018 January Bronze 3] Out Of Place

TruaTheOrca Feb 14th, 2020 99 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. PROBLEM: http://www.usaco.org/index.php?page=viewproblem2&cpid=785
2. CODE: https://pastebin.com/qvDGP0Dw
3.
4. In a normal situation, the cows would be sorted. (For the example on the site, the original ordering of cows is as so:)
5. SORTED: [2, 3, 4, 7, 7, 9]
6. CURRENT:[2, 4, 7, 7, 9, 3]
7.
8. We would like to swap pairs of cows until the current array is equal to sorted array.
9. To put 2 cows in their proper order, it would take 1 swap.
10. To put 3 cows in their proper order, it would take 2 swaps.
11. Therefore, the number of swaps required == numbers out of place -1. (In this case, 3.)
12.
13. Solution:
14. 1. Read in current array.
15. 2. Make copy of current array and sort.
16. 3. Keep a count (answerCount in my code) and loop through size of array. If current[i] != sorted[i], answerCount++.