Educational Codeforces Round 3 D – Gadgets for dollars and pounds
链接: https://codeforces.com/contest/609/problem/D
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 |
public class TaskD { public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); // numbers of days int m = in.readInt(); // total number of gadgets int k = in.readInt(); // required number of gadgets long s = in.readLong(); // number of $ int[] dollar = in.readIntArray(n); int[] pound = in.readIntArray(n); Pair<Integer, Integer>[] res = new Pair[k]; Item[] items = new Item[m]; for (int i = 0; i < m; i++) { items[i] = new Item(); items[i].type = in.readInt(); items[i].cost = in.readInt(); items[i].pos = i; } int start = 0; int end = n-1; int minDay = -1; while (end >= start) { int mid = start + (end -start) / 2; if (canDo(mid, dollar, m, k, s, pound, items, res)) { minDay = mid; end = mid - 1; } else { start = mid +1; } } if (minDay == -1) { out.printLine("-1"); } else { out.printLine(minDay+1); for (int i = 0; i < k; i++) { out.printLine((res[i].first+1)+" "+(res[i].second+1)); } } } private boolean canDo(int cur, int[] dollar, int m, int k, long s, int[] pound, Item[] items,Pair<Integer, Integer>[] res) { int dayD = -1; int dayP = -1; int minD = Integer.MAX_VALUE; int minP = Integer.MAX_VALUE; for (int i = 0; i <= cur; i++) { if (dollar[i] < minD) { minD = dollar[i]; dayD = i; } if (pound[i] < minP) { minP = pound[i]; dayP = i; } } for (int i = 0; i < m; i++) { if (items[i].type == 1){ items[i].need = BigDecimal.valueOf(minD).multiply(BigDecimal.valueOf(items[i].cost)); } else { items[i].need = BigDecimal.valueOf(minP).multiply(BigDecimal.valueOf(items[i].cost)); } } Arrays.sort(items); // sort by the required burles BigDecimal sum = new BigDecimal(0); for (int i = 0; i < k; i++) { sum = sum.add(items[i].need); } if (sum.compareTo(new BigDecimal(s)) <= 0) { for (int i = 0; i < k; i++) { if (items[i].type == 1) { res[i] = Pair.makePair(items[i].pos,dayD); } else { res[i] = Pair.makePair(items[i].pos,dayP); } } return true; } else { return false; } } class Item implements Comparable<Item> { int type; int cost; int pos; BigDecimal need; @Override public int compareTo(Item o) { return need.compareTo(o.need); } } } |
这题好tricky, 好几个test都是c++的ll类型的, java做着好头疼.
首先根据题意可以看出来, 能在x天完成任务(从m中买到k个item), 在剩下的x+1天也能完成, 所以具有单调性, 可以在排序(根据买东西的实际价格排序, 这里的实际价格是第i天的汇率*单价).
其次我们的目标是买k个东西, 那么如果给定某天x, 如何用同样的钱(假设), 买更多的东西?, 肯定是先买便宜的啊. 所以是贪心算法. 既然是贪心算法, 我们就要找到算法的关键, 那就是如何在m天中的第i天买到更便宜的东西? 显然, 我们知道汇率和单价是乘法关系, 就要分别找到前i天的两种货币的最低汇率minD和minP, 然后我们要测试一下在cur天的时候, 我们能否买够所需的k个物品. 这里我们用minD和minP分别乘以m个物品, 然后得到的价格就是cur天实际价格, 然后通过排序并且提取前k个物品, 我们就可以测试能否在cur天购买到k个物品.
Leave A Comment