专业的郑州网站推广,多用户网站建设,wordpress 社区,保定做网站建设http://poj.org/problem?id2976 题目大意#xff1a;给定n个二元组(a,b)#xff0c;扔掉k个二元组#xff0c;使得剩下的 最大。 这两天一直在搞分数规划#xff0c;有了前两道题#xff08;3621、2728#xff09;#xff0c;这道题就是完完全全的大水题了。 设 r100… http://poj.org/problem?id2976 题目大意给定n个二元组(a,b)扔掉k个二元组使得剩下的 最大。 这两天一直在搞分数规划有了前两道题3621、2728这道题就是完完全全的大水题了。 设 r100*∑(ai)/∑(bi) 有 100*∑(ai)-r*∑(bi)0 ∑(100*ai-r*bi)0 这个东西是单调的…… 我们可以将每个二元组的得分设为100*a-r*b然后从大到小排序取前n-k个得分求和(sum)。若sum0则说明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 ab;}int main(){while(scanf(%d%d,n,k),nk){for(int i1;in;i) scanf(%d,a[i]);for(int i1;in;i) scanf(%d,b[i]);double low0,high100,mid;while(high-loweps){mid(lowhigh)/2.0;for(int i1;in;i) score[i]a[i]*100.0-b[i]*mid;sort(score1,scoren1,cmp);double sum0;for(int i1;in-k;i) sumscore[i];if(sum0) lowmid;else highmid;}cout(int)(low.5)endl;}return 0;
}转载于:https://www.cnblogs.com/Delostik/archive/2011/07/28/2119404.html
