Link to pdf version on UVa OJ
There are two lists (knights, dragonParts) that we want to match them (one by one). All of the dragonParts must have exactly one match from the knights list. Some knights may have no matches. We must do the matching in a way that total sum of the knights that have a match is minimized.
Knight i can be matched with dragonPart j if and only if knight[i] >= dragonPart[j].
What happened in my mind : As I saw there are two lists and one "must" have matches I thought it's a good idea to sort both of them and think about them after that. After sorting I looked at the first dragonPart, no matter what, if we want to have the final match we "must" find a match for this first dragonPart. Put another pointer at the beginning of knights array. Can the first knight satisfy this dragonPart? If Yes, we take it, because this is the minimum cost we can pay for the first dragonPart. If we skip this knight and look for another (more expensive) knight we are already losing money.
If No, we can skip this knight altogether, because when this knight cannot satisfy the minimum dragonPart, it definitely cannot satisfy any dragonPart bigger than this one.
This is called a two-pointer approach.
This is also called a greedy solution, because when we are matching a dragonPart and a knight we decide greedily and move on and never look back at what we decided in previous steps. We just try to make the best decision and move on. ( Like life! ;) )
For more details look at my code on github
p.s. A classical problem solved by two-pointer is a sorted list and a number X. The question is that whether we can find a pair than sums up to X?
There are two lists (knights, dragonParts) that we want to match them (one by one). All of the dragonParts must have exactly one match from the knights list. Some knights may have no matches. We must do the matching in a way that total sum of the knights that have a match is minimized.
Knight i can be matched with dragonPart j if and only if knight[i] >= dragonPart[j].
What happened in my mind : As I saw there are two lists and one "must" have matches I thought it's a good idea to sort both of them and think about them after that. After sorting I looked at the first dragonPart, no matter what, if we want to have the final match we "must" find a match for this first dragonPart. Put another pointer at the beginning of knights array. Can the first knight satisfy this dragonPart? If Yes, we take it, because this is the minimum cost we can pay for the first dragonPart. If we skip this knight and look for another (more expensive) knight we are already losing money.
If No, we can skip this knight altogether, because when this knight cannot satisfy the minimum dragonPart, it definitely cannot satisfy any dragonPart bigger than this one.
This is called a two-pointer approach.
This is also called a greedy solution, because when we are matching a dragonPart and a knight we decide greedily and move on and never look back at what we decided in previous steps. We just try to make the best decision and move on. ( Like life! ;) )
For more details look at my code on github
p.s. A classical problem solved by two-pointer is a sorted list and a number X. The question is that whether we can find a pair than sums up to X?
No comments:
Post a Comment