A. 摘水果 (fruit)

输入输出样例

样例1

输入

3
3 9 4 1 3 4
0 0 2 0 4 4

输出

7 13 2

题解一：模拟

模拟。维护两个队列分别存储候选果子（每次摘从中选择）和受限的果子（暂时不能摘），每次摘完更新果子的状态和两个队列。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        final int n = 2 * Integer.parseInt(reader.readLine());
        int[] a = new int[n];
        int[] b = new int[n];
        String[] strs = reader.readLine().split(" ");
        for (int i = 0; i < n; ++i) {
            a[i] = Integer.parseInt(strs[i]);
        }
        strs = reader.readLine().split(" ");
        for (int i = 0; i < n; ++i) {
            b[i] = Integer.parseInt(strs[i]);
        }
        long start = System.currentTimeMillis();
        Fruit[] fruits = new Fruit[n + 1];
        for (int i = 1; i <= n; ++i) {
            fruits[i] = new Fruit(i, a[i - 1], b[i - 1]);
        }
        for (int i = 1; i <= n; ++i) {
            if (b[i - 1] > 0) {
                ++fruits[b[i - 1]].cnt;
            }
        }
        // 候选果子
        List<Fruit> doList = new ArrayList<Fruit>(n);
        // 受限的果子
        List<Fruit> undoList = new ArrayList<Fruit>(n);
        for (int i = 1; i <= n; ++i) {
            fruits[i].update();
            if (fruits[i].isWork) {
                doList.add(fruits[i]);
            } else {
                undoList.add(fruits[i]);
            }
        }
        List<Integer> ans = new ArrayList<Integer>(n);
        while (!doList.isEmpty()) {
            Pair max = null;
            for (int i = 0; i < doList.size(); ++i) {
                // 选苹果
                if (doList.get(i).id > n / 2) {
                    continue;
                }
                for (int j = 0; j < doList.size(); ++j) {
                    // 选梨
                    if ((i == j) || (doList.get(j).id <= n / 2)) {
                        continue;
                    }
                    Pair pair = new Pair(doList.get(i), doList.get(j));
                    if (pair.compareTo(pair, max) > 0) {
                        max = pair;
                    }
                }
            }
            ans.add(max.val);
            for (Iterator<Fruit> it = doList.iterator(); it.hasNext();) {
                Fruit tmp = it.next();
                if ((tmp.id == max.apple.id) || (tmp.id == max.pear.id)) {
                    if (tmp.next > 0) {
                        --fruits[tmp.next].cnt;
                    }
                    it.remove();
                }
            }
            for (Iterator<Fruit> it = undoList.iterator(); it.hasNext();) {
                Fruit tmp = it.next();
                tmp.update();
                if (tmp.isWork) {
                    doList.add(tmp);
                    it.remove();
                }
            }
        }
        for (int i = 0; i < ans.size() - 1; ++i) {
            System.out.print(ans.get(i) + " ");
        }
        System.out.println(ans.get(ans.size() - 1));
        System.out.println(System.currentTimeMillis() - start + "ms");
    }
}
class Pair {
    Fruit apple;
    Fruit pear;
    int val;
    public Pair(Fruit o1, Fruit o2) {
        apple = o1;
        pear = o2;
        val = o1.val ^ o2.val;
    }
    public int compareTo(Pair o1, Pair o2) {
        if (o1 == null) {
            return -1;
        }
        if (o2 == null) {
            return 1;
        }
        if (o1.val > o2.val) {
            return 1;
        } else if (o1.val < o2.val) {
            return -1;
        }
        if (o1.apple.val > o2.apple.val) {
            return 1;
        } else if (o1.apple.val < o2.apple.val) {
            return -1;
        }
        if (o1.apple.id > o2.apple.id) {
            return 1;
        } else if (o1.apple.id < o2.apple.id) {
            return -1;
        }
        if (o1.pear.id > o2.pear.id) {
            return 1;
        } else if (o1.pear.id < o2.pear.id) {
            return -1;
        }
        return 0;
    }
}
class Fruit {
    // 水果编号
    int id;
    // 美味度
    int val;
    // 关联的水果编号
    // 0表示无效
    int next;
    // 被关联的水果数量
    int cnt;
    // 是否可以摘取
    boolean isWork;
    public void update() {
        if (cnt == 0) {
            isWork = true;
        }
    }
    public Fruit(int id, int val, int next) {
        super();
        this.id = id;
        this.val = val;
        this.next = next;
        this.cnt = 0;
        this.isWork = false;
    }
}