发布于2018年8月17日2018年8月19日 由itewqq[01分数规划][二分][精度][坑] POJ2976 Dropping tests 二分答案倒是容易想到，实现的话需要排序后贪心，但是坑在精度上 我用了printf(“%.0f\n”,ans); WA cout<<(int )(ans+0.5)<<endl; AC 就很玄学。。。。学到了学到了 //#include #include #include #include #include #include #include #include #include #include #include #include #include #include //#include #define eps (1e-6) using namespace std; typedef long long LL; const int maxn=1e3+5; const int MOD=1e9+7; const int INF=0x4f4f4f4f; void read(int &x) { char ch = getchar(); x = 0; for (; ch < '0' || ch > '9'; ch = getchar()); for (; ch >='0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0'; } int a[maxn],b[maxn]; int n,k; double tmp[maxn]; int check(double d) { for (int i=1;i<=n;i++) tmp[i]=100.0*a[i]-d*b[i]; sort(tmp+1,tmp+1+n); double sum=0.0; for (int i=n;i>k;i--) sum=sum+tmp[i]; if(sum>eps)//try 0? return 1; else return 0; } int main() { //freopen("1.txt","r",stdin); //freopen("2.txt","w",stdout); while(~scanf("%d%d",&n,&k)&&n) { for (int i=1;i<=n;i++) scanf("%d",&a[i]); for (int i=1;i<=n;i++) scanf("%d",&b[i]); double l=0.0,r=100.0,mid; while(r-l>0.0001) { mid=(l+r)/2; if(check(mid)) l=mid; else r=mid-0.0001; } cout<<(int)(r+0.5)<
