poj2976(二分,最大值平均化模板)Dropping tests

xiaoxiao2021-02-28  87

/* 浮点数的精度问题是通过多次循环实现的 (n-k)个数,最大化平均值 */ #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int mn=1005; int n,m,a[mn],b[mn]; double y[mn]; bool iswork(double x) { for(int i=0;i<n;++i) y[i]=a[i]-x*b[i]; sort(y,y+n,greater<int>()); double sum=0; for(int i=0;i<m;++i) sum+=y[i]; return sum>=0.0; } void solve() { double l=0,r=1e9; int cnt=100;//100次的循环精度可以达到10^(-30)的精度范围 while(cnt--) { double mid=(l+r)/2; if(iswork(mid)) l=mid; else r=mid; } printf("%.0f\n",l*100);//在做题时printf最好用%f,否则可能出现一些莫名其妙的错误 } int main(){ while(~scanf("%d%d",&n,&m)&&(n||m)) { m=n-m; for(int i=0;i<n;++i) scanf("%d",a+i); for(int i=0;i<n;++i) scanf("%d",b+i); solve(); } return 0; }

转载请注明原文地址: https://www.6miu.com/read-62924.html

最新回复(0)