POJ 3111 K Best

二分，排序，贪心。

最优比率生成树，可以二分$+$贪心来实现，不过这样做精度不行。

如果是这样一个问题，该如何解决：问你$n$个里面选择$k$个，能否使得$\frac{{\sum\limits_{j = 1}^k {{v_{{i_j}}}} }}{{\sum\limits_{j = 1}^k {{w_{{i_j}}}} }} ≥ x$。

上述问题等价于问你：$n$个里面选择$k$个，能否使得$\sum\limits_{j = 1}^k {({v_{{i_j}}} - x×{w_{{i_j}}})} ≥ 0$。

也就是说，我们需要令${f_i} = {v_i} - x×{w_i}$，按照${f_i}$从大到小排序，选择前$k$个计算和$sum$。

如果$sum≥0$，也就是说$\frac{{\sum\limits_{j = 1}^k {{v_{{i_j}}}} }}{{\sum\limits_{j = 1}^k {{w_{{i_j}}}} }} ≥ x$成立；否则不成立。

因为这个问题是遵循单调性的，$x$越大可能性越小，因此只要二分$x$，然后验证就可以了。时间复杂度$O(50*n*\log n)$。

特别要注意的是精度问题：

$[1].$计算$sum$的时候，最后要加上一个$eps$，我在这卡了很久精度。

$[2].$二分的话差不多$50$次就可以了，$100$次$TLE$了，也没有必要进行$100$次，因为实际上是只要$\log {10^7}$次。

#pragma comment(linker, "/STACK:1024000000,1024000000")

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<vector>

#include<map>

#include<set>

#include<queue>

#include<stack>

#include<iostream>

using namespace std;

typedef long long LL;

const double pi=acos(-1.0),eps=1e-;

void File()

{

    freopen("D:\\in.txt","r",stdin);

    freopen("D:\\out.txt","w",stdout);

}

template <class T>

inline void read(T &x)

{

    char c = getchar(); x = ;while(!isdigit(c)) c = getchar();

    while(isdigit(c)) { x = x *  + c - ''; c = getchar();  }

}

const int maxn=;

struct X { int v,w;}s[maxn];

int n,k,ans[maxn];

struct XX {double num; int id;}t[maxn];

double Max;

bool cmp(XX a,XX b){ return a.num>b.num; }

bool check(double x)

{

    for(int i=;i<=n;i++)

    {

        t[i].num=1.0*s[i].v-x*s[i].w;

        t[i].id=i;

    }

    sort(t+,t++n,cmp);

    double sum=;

    for(int i=;i<=k;i++) sum=sum+t[i].num;

    if(sum+eps>=)

    {

        for(int i=;i<=k;i++) ans[i]=t[i].id;

        return ;

    }

    return ;

}

int main()

{

    while(~scanf("%d%d",&n,&k))

    {

        for(int i=;i<=n;i++)

            scanf("%d%d",&s[i].v,&s[i].w);

        double L=0.0,R=10000000.0;

        int t=;

        while(t--)

        {

            double mid=(L+R)/;

            if(check(mid)) L=mid;

            else R=mid;

        }

        for(int i=;i<=k;i++)

        {

            printf("%d",ans[i]);

            if(i<k) printf(" "); else printf("\n");

        }

    }

    return ;

}

巴特西

POJ 3111 K Best

最新文章

热门文章