p4377专题

POJ2976 Dropping tests——P4377 [USACO18OPEN] Talent Show G 【分数规划二分法+贪心/背包】

POJ2976 Dropping tests        【分数规划二分法+贪心】 有 n 个物品,每个物品有两个权值 a 和b。你可以放弃 k 个物品,选 n-k 个物品,使得最大。 输入多个样例,第一行输入n 和 k,第二行输入n 个 ai ,第三行输入 n 个 bi,输入 0 0 结束。 输出答案乘100 后四舍五入到整数的值。 数据范围:1<=n<=1000,0<=k<n,0<=ai<=