题目链接
题解
刚才写的分数规划的裸题.
我们要求最优解,还要去掉不好的\(k\)个.
所以直接贪心,暴力取\(All[i]\)最大的.把较小的\(k\)个去掉.
然后二分出一个\(mid\)满足表达式等于0的.最后输出.
但是,我想说poj毒瘤
记得要保证读进来的\(n,k\)不等于0 .
而且还不能写成
|
1 2 3 4 |
while(scanf("%d%d",&n,&k)&&n&&k){ //... } |
这样会WA…
QAQ
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
#include<cstdio> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> using namespace std ; template<class T>void read(T &x){ x=0;int f=0;char ch=getchar(); while(ch<'0'||ch>'9'){f|=(ch=='-');ch=getchar();} while(ch<='9'&&ch>='0'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} x=f?-x:x; return ; } const double eps=1e-4; const int maxn=1003; double val[maxn],cost[maxn],all[maxn],M; int n,k; void init(){ memset(all,0,sizeof(all)); memset(val,0,sizeof(val)); memset(cost,0,sizeof(cost)); M=0; } int main() { freopen("a.in","r",stdin); freopen("a.out","w",stdout); while(scanf("%d%d",&n,&k)){ if(!n&&!k) break; init(); for(int i=1;i<=n;i++) scanf("%lf",&val[i]); for(int i=1;i<=n;i++) scanf("%lf",&cost[i]); double l=0.0,r=1.0; while(r-l>eps){ M=(l+r)*1.0/2; for(int i=1;i<=n;i++) all[i]=val[i]-cost[i]*M; sort(all+1,all+1+n);double sum=0; for(int i=k+1;i<=n;i++) sum+=all[i]; if(sum<=0) r=M; else l=M; } printf("%.0lf\n",M*100); } return 0; } |
By:Wahacer
2017.12.21
21:44