K Best（最大化平均值）

題目連結：https://cn.vjudge.net/contest/279225#problem/H

題目大意：這個Demy由于家庭經濟困難了，是以要賣掉她n個珠寶中的一部分來維持家庭生活，但是她想留下平均價值最高的k個珠寶，然後要我們幫她算要留下哪些珠寶才能達到目的。

這個就是跟上道題一樣的推個式子就完事了，我就不再寫了，求和符号好難打耶，直接看上一篇嘛：https://blog.csdn.net/weixin_44049850/article/details/86562201

直接貼代碼了哦

#include <stdio.h>
#include <algorithm>
#define INF 100005
#define MAX 0x3f3f3f3f
using namespace std;
int n,k;
struct node
{
    double v,w,tcmp;
    int IP;
} a[INF];
bool cmp(node n1,node n2)
{
    return n1.tcmp>n2.tcmp;
}
bool judge(double x)
{
    double ans=0;
    for(int i=0; i<n; i++)
    {
        a[i].tcmp=a[i].v-a[i].w*x;
    }
    sort(a,a+n,cmp);
    for(int i=0; i<k; i++)
    {
        ans+=a[i].tcmp;
    }
    return ans>=0;
}
int main()
{
    while(~scanf("%d%d",&n,&k))
    {
        for(int i=0; i<n; i++)
        {
            scanf("%lf%lf",&a[i].v,&a[i].w);
            a[i].IP=i+1;//這個IP就是存是第幾個珠寶的，在剛開始輸入的時候把這個值給附上，後邊即使排序這個值也不會變，我剛開始不知道咋想的把這個的指派放在了judge函數裡，是以wa了一發……，就是這兒嘛需要注意一下，其他就沒什麼了，跟上道題是一樣的
        }
        double max_,min_,mid;
        max_=MAX;
        min_=0;
        while(max_-min_>=1e-8)
        {
            mid=(max_+min_)/2;
            if(judge(mid))
                min_=mid;
            else
                max_=mid;
        }
        for(int i=0; i<k; i++)
            printf("%d%c",a[i].IP," \n"[i==k-1]);
    }
    return 0;
}