nwhitcher The description would be clearer if it read "L is the amount of luck that can be gained by losing the contest." She believes that luck is spent on wins and earned from losses.
acfromspace My updated Python3 solution:
def luckBalance(k, contests): # sort from greatest luck to least luck contests.sort(reverse=True) luck = 0 for contest in contests: if contest[1] == 0: luck += contest[0] elif k > 0: luck += contest[0] k -= 1 else: luck -= contest[0] return luck
It took a lot of whiteboarding to clearly put out what I wanted. Sorted the nested list by the first value, number of points, and from there chose which points I wanted to add and which points I needed to subtract. Thanks to @hubrando for the code review, took out an unnecessary variable and utilized an existing one.
SnoopDizzle I learned a funny thing by doing this... in C++, the vector.size() method returns an unsigned int, so subtraction might silently wrap around to a large number, instead of a negative one. I can't believe I've never encountered this problem before...
tao_zhang This is the same problem I have done in Week Of Code 21. I copied my solution in Java:
import java.util.*; public class Solution { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int k = scanner.nextInt(); int total = 0; List<Integer> importantContests = new ArrayList<>(); for (int i=0; i<n; i++){ int luck = scanner.nextInt(); int importance = scanner.nextInt(); total += luck; if (importance == 1) { importantContests.add(luck); } } Collections.sort(importantContests); int luckToFlip = 0; int mustWinImprCount = importantContests.size() - k; for (int i=0; i<mustWinImprCount; i++){ luckToFlip += importantContests.get(i); } int result = total - 2*luckToFlip; System.out.println(result); } }
Dmoneyskbow I solved the problem fine, but could someone help me understand why this is a greedy algorithm?
Sort 569 Discussions, By:
Please Login in order to post a comment