[POJ2976] Dropping tests

题意

n个二元组(ai,bi)$(a_i,b_i)$，选定n-K个二元组使得∑ai∑bi$/frac{/sum a_i}{/sum b_i}$最大

题解

基本的01分数规划问题 weighti=valuei−r⋅costi$weight_i = value_i-r/cdot cost_i$，max{f(r)}$max/{f(r)/}$求和前n+K大的weighti$weight_i$即可。 至于为什么WA嘛，改改精度，c++与g++都试试，多试几遍就AC了。 另外： 精度误差处理方式 设ε$/varepsilon$为精度误差，越小精度越高，如ε=10−8$/varepsilon = 10^-8$，程序中经常将它写为eps=1E-8 减少精度误差的方法： a=b⇔|a−b|<ε$a=b /Leftrightarrow |a-b|</varepsilon$ a<b⇔a−b<−ε$a<b /Leftrightarrow a-b<-/varepsilon$ a≤b⇔a−b<ε$a/le b /Leftrightarrow a-b</varepsilon$

代码