题目链接: https://codeforces.com/problemset/problem/282/B
官方题解: https://codeforces.com/blog/entry/6999
CF 282B 我思考了很久，也没有什么头绪。看了官方题解，发现可以用一个很简单的贪心算法求解。证明的过程要用到数学归纳法(Mathematical induction)，我按照我的理解，把证明过程详细地写下来。
贪心算法：对于每一个鸡蛋，尝试让 A 喷绘。如果这会导致让 A 的收入高于 G 的收入，且超出了 500 的幅度，则把这个鸡蛋交给 G。
引理1：对于合法的输入数据，一定存在至少一种方法，使得两人的收入和之差 \(|S_a - S_g| \leq 500\)
求证：使用贪心算法，可以得到正确解。
Base case is trivial.
递推步骤，假设对于前 i-1 个鸡蛋，我们已经找到了一种方法，满足
\(|S_a - S_g| \leq 500\)
。不失一般性 (WLOG)，我们假定
\(S_a - S_g = D\)
且
\(0 \leq D \leq 500\)
现在，我们尝试将第 i 个鸡蛋分配给 A. 如果
\(D + a_i \leq 500\)
仍然成立，那我们就得到了满足前 i 个鸡蛋的合法方案。
反之，我们将第 i 个鸡蛋分配给 G。此时，
\(a_i > 500 - D \iff 1000 - g_i > 500 - D \iff g_i < 500 + D\)
新的差值是
\(D_i = (S_g + g_i) - S_a = g_i - D\)
显然
\(-D \leq D_i < 500\)
我们就得到了满足前 i 个鸡蛋的合法方案。
引理1 也由此得到了证明。Base case 选择一个报酬不超过 500 元的人，接着每次扩展，都不会打破 500 元工资差的限制。
弯路
看答案之前，我没有想到引理1. 我猜到这是一道贪心的题目，但题目里的“无法满足时输出-1”迷惑了我，让我一直在想，我的贪心策略会不会让一个可行的输入被误认为不可能。
我一直试图寻找一个给输入数据排序的方法，接着用类似对对碰的方式进行贪心匹配。我一直试图找一个例子，证明错误的贪心顺序会导致错误。最终当然是找不到了。
这道题给定的限制条件是不超过 500 的工资差，而两人的工资和则恰巧是 1000 元。这其实给了我很大的提示，两人的工资差可能是钟摆式的摆动，但我没有顺着这个思路思考下去。
我在做这道题的时候，一度试图把 500 元的条件拿掉，去找一个让两人工资差最低的方案。我成功地给自己找了一个困难得多的问题。