nyoj914(二分搜索+貪心)

nyoj914(二分搜索+貪心)

題目意思：

acm.nyist.net/JudgeOnline/problem.php?pid=914

現在有n個物品的重量和價值分別是Wi和Vi，你能幫他從中選出k個物品使得單位重量的價值最大嗎？

輸入有多組測試數據
每組測試數據第一行有兩個數n和k，接下來一行有n個數Wi和Vi。
(1<=k=n<=10000) (1<=Wi,Vi<=1000000)輸出輸出使得單位價值的最大值。（保留兩位小數）樣例輸入

3 2
2 2
5 3
2 1

樣例輸出

0.75

題目分析：

此題直接對單價進行貪心會出現問題，而且不難從樣例上看出來。由於k個物品的單價一定不大於最大單價的物品，

而且一定會大於0，因此可以用二分搜素+貪心來解題。具體細節見注釋

AC代碼：

/**
*貪心+二分搜索
*/
#include
#include
#include
#include
#define exp 1e-5
using namespace std;
typedef struct node{
double w,v;
}node;
node p[10005];
double y[10005];
int n,k;
int cmp(double a,double b){
if(a>b) return 1;
return 0;
}
int Judge(double x){//二分搜索最大的且最恰當的值是否合理，if(合理)證明還有繼續加大的空間，可以繼續增大
for(int i=0;i y[i]=p[i].v-p[i].w*x;
}
sort(y,y+n,cmp);
double s=0;
for(int i=0;i s+=y[i];
}
if(s>=0) return 1;
else return 0;
}
double Search(double ma){
double l=0,r=ma;
while(r-l>exp){
double mid=(l+r)/2;
if(Judge(mid)){//當前值還小,還要增大
l=mid;
}
else{//當前值大了,需要減小
r=mid;
}
}
return l;//或者return r;此時l=r
}
int main()
{
while(scanf("%d%d",&n,&k)!=EOF){
double ma=0;//k個最大平均值一定小於等於單個最大價值且大於0
for(int i=0;i scanf("%lf%lf",&p[i].w,&p[i].v);
if(ma }
printf("%.2lf\n",Search(ma));
}
return 0;
}