[POJ2976] Dropping tests

2019-11-11 02:54:20

字體：大中小

來源：轉載

供稿：網友

題意

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$

代碼

/// by ztx/// blog.csdn.net/hzoi_ztx#define Rep(i,l,r) for(i=(l);i<=(r);i++)#define rep(i,l,r) for(i=(l);i< (r);i++)#define Rev(i,r,l) for(i=(r);i>=(l);i--)#define rev(i,r,l) for(i=(r);i> (l);i--)#define Each(i,v) for(i=v.begin();i!=v.end();i++)#define r(x) read(x)typedef long long ll ;typedef double lf ;int CH , NEG ;template <typename TP>inline void read(TP& ret) { ret = NEG = 0 ; while (CH=getchar() , CH<'!') ; if (CH == '-') NEG = true , CH = getchar() ; while (ret = ret*10+CH-'0' , CH=getchar() , CH>'!') ; if (NEG) ret = -ret ;}#define maxn 1010LL#define eps 1E-4int n, K;lf v[maxn], c[maxn], w[maxn], L, M, R, maxf;int main() { int i; while (scanf("%d%d", &n, &K), n|K) { Rep (i,1,n) scanf("%lf", &v[i]); Rep (i,1,n) scanf("%lf", &c[i]); L = 0, R = 100; while (R-L > eps) { // L:maxf>0 , R:maxf<=0 M = (L+R)/2; Rep (i,1,n) w[i] = v[i]*100-M*c[i]; std::sort(w+1,w+n+1); maxf = 0; rev (i,n,K) maxf += w[i]; if (maxf > eps) L = M; else R = M; }