http://poj.org/problem?id=2976

　　題目大意：給定n個二元組(a,b)，扔掉k個二元組，使得剩下的? ?最大。

　　這兩天一直在搞分數規劃，有了前兩道題（3621、2728），這道題就是完完全全的大水題了。

　　設 r=100*∑(ai)/∑(bi) ，有

　　　　100*∑(ai)-r*∑(bi)=0

　　　　∑(100*ai-r*bi)=0

　　這個東西是單調的……

　　我們可以將每個二元組的得分設為100*a-r*b，然后從大到小排序，取前n-k個得分求和(sum)。若sum>0則說明r還不夠大，可以向上二分；反之向下二分……

　　我最討厭精度什么的了……尤其是C++的精度……

#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <algorithm> #define eps 1e-4 using namespace std;double score[1005]; int a[1005],b[1005],n,k; bool cmp(double a,double b){return a>b;}int main(){while(scanf("%d%d",&n,&k),n+k){for(int i=1;i<=n;i++) scanf("%d",&a[i]);for(int i=1;i<=n;i++) scanf("%d",&b[i]);double low=0,high=100,mid;while(high-low>eps){mid=(low+high)/2.0;for(int i=1;i<=n;i++) score[i]=a[i]*100.0-b[i]*mid;sort(score+1,score+n+1,cmp);double sum=0;for(int i=1;i<=n-k;i++) sum+=score[i];if(sum>0) low=mid;else high=mid;}cout<<(int)(low+.5)<<endl;}return 0; }

　　

轉載于:https://www.cnblogs.com/Delostik/archive/2011/07/28/2119404.html

總結

以上是生活随笔為你收集整理的POJ 2976 Dropping Tests的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。