题目
题目大意
有 \(N\) 种饭菜，每种饭菜有两种价格 \(A_i\) 和 \(B_i\) 。对于两种价格，如果你的选的第一道菜是 \(i\) ，则它的价格为 \(A_i\) 否则为 \(B_i\) ,求对于点 \([1,N]\) 道菜所需的最低价格 。 不管点菜的顺序，不会点两道同样的菜 。
思路
考虑贪心。
zhx说的好，遇事不决先排序 。
因为不管点菜的顺序，所以我们将 \(B_i\) 按从小到大的顺序拍一遍序，显然，对于 \(B_i\) 较小是更优的。我们可以取出前 \(k-1\) 个 \(B_i\) 和第 \(N-k+1\) 个 \(A_i\) 。 \(sum_i \ = \ (\sum_{i=1} ^{k-1}b_i ) + (\min_{i=k}^n a_i)\)
这样就够了？显然不是。例如这么一组数据
4
1 2
114514 15
1919810 8
1145141919810 45
如果我们按照上面的方法计算的话，例如当 \(k=2\)
也就是说，对于后面的 \(A_i\) 的值很大的时候，这样就不够优了 。
未完待续。。。。
标签：P8298,题解,sum,COCI2012,POPUST,2013 From： https://www.cnblogs.com/Alwaysmaxx/p/16786316.html