題意

n個(gè)二元組(ai,bi)$(a_i,b_i)$，選定n-K個(gè)二元組使得∑ai∑bi$/frac{/sum a_i}{/sum b_i}$最大

題解

基本的01分?jǐn)?shù)規(guī)劃問題 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了。 另外： 精度誤差處理方式 設(shè)ε$/varepsilon$為精度誤差，越小精度越高，如ε=10?8$/varepsilon = 10^-8$，程序中經(jīng)常將它寫為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$

代碼