NYOJ 586 瘋牛&NYOJ 914 Yougth的最大化 （二分+貪心）

NYOJ 586    瘋牛

#include<stdio.h>
#include<algorithm>
using namespace std;
int a[100010],n,c;
bool greed( int t)
{
    int i,j=a[0],count=0;
    for(i=0;i<n;i++)
    {
        if(a[i]-j>=t) {j=a[i];  count++;}
        if(count>=c-1) return true;

    }
    return false;
}
void binary_search()
{
    int front=0,end=a[n-1]-a[0];
    int mid;

    while(front<=end)
    {
        mid=(front + end )/2;
        if(greed(mid))
            front=mid+1;
           else end=mid-1;
    }
    printf("%d\n",front-1);
}
int main()
{
    int i;
    while(scanf("%d %d",&n,&c)!=EOF)
    {
        for(i=0;i<n;i++)
          scanf("%d",&a[i]);
          sort(a,a+n);
          binary_search();
    }
    return 0;
}
        
           

NYOJ 914  Yougth的最大化

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 11000;
int w[N],v[N];
double y[N];
int n,c;
int chack(double x)
{
    for(int i=0;i<n;i++)
    {
        y[i]=v[i]-x*w[i];
    }
    sort(y,y+n);
    double sum=0;
    for(int i=0;i<c;i++)
    {
        sum+=y[n-i-1];
    }
    return sum>=0;
}
double reaerch(double enf)
{
    double l=0,r=enf,mid;
    for(int i=0;i<100;i++)//資料精确細化
    {
        mid=(l+r)/2;
        if(chack(mid))
            l=mid;
        else
            r=mid;
    }
    return l;
}
int main()
{
    while(~scanf("%d%d",&n,&c))
    {
        double ma=0;
        for(int i=0;i<n;i++){
            scanf("%d%d",&w[i],&v[i]);
            double cmp=v[i]/w[i];
            if(cmp>ma)
                ma=cmp;
        }
        printf("%.2lf\n",reaerch(ma));
    }
    return 0;
}