P1080[NOIP2012提高组]国王游戏题目恰逢H国国庆，国王邀请\(n\)位大臣来玩一个有奖游戏。首先，他让每个大臣在左、右手上面分别写下一个整数，国王自己也在左、右手上各写一个整数。然后，让这\(n\)位大臣排成一排，国王站在队伍的最前面。排好队后，所有的大臣都会获得国王奖赏的

每次都选当下的最优解，一步步得到全局的最优。可以贪心的题目的性质最优子结构性质：选择当前问题的最优决策不会影响子问题的最优决策。贪心选择性：当前决策依赖于已经做出的决策，且决策一旦做出边不能更改。证明贪心策略正确的方法反证法：如果交换某两个元素后不会得到更