Educational Codeforces Round 3 D – Gadgets for dollars and pounds

链接: https://codeforces.com/contest/609/problem/D

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个物品.