(IOI) 2009 Day 1 p2 Hiring

https://contest.yandex.com/ioi/contest/1362/problems/B/

可以先用二分搜來確認人數。

人數確認好了後，可以好好的利用比例的關係(?)去做比較，就可以找出最小值的答案這樣。

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<LL,LL> pii;
const int N = 500006;

#define F first
#define S second

pii p[N];
int v[N];
int n;
LL w;

vector<int> vv;

bool doo(int mid,bool get_ans = false)
{
    priority_queue<pii> pq;
    LL tot=0;
    for (int i=1;mid-1>=i;i++)
    {
        pq.push(make_pair(p[ v[i] ].S , v[i]) );
        tot += p[ v[i] ].S;
    }
    bool ret = false;
    pii ww = make_pair(w,1);
    int ii = -1;
    for (int i=mid;n>=i;i++)
    {
        if (p[ v[i] ].F * (tot + p[ v[i] ].S) * ww.S <= p[ v[i] ].S*ww.F)
        {
            ret = true;
            ii = i;
            ww = make_pair(p[ v[i] ].F * (tot + p[ v[i] ].S) , p[ v[i] ].S);
        }
        if (mid != 1 && p[ v[i] ].S < pq.top().F)
        {
            tot -= pq.top().F;
            pq.pop();
            pq.push(make_pair(p[ v[i] ].S,v[i]));
            tot += p[ v[i] ].S;
        }
    }
    if (get_ans)
    {
        while (!pq.empty()) pq.pop();
        tot=0;
        for (int i=1;mid-1>=i;i++)
        {
            pq.push(make_pair(p[ v[i] ].S , v[i]) );
            tot += p[ v[i] ].S;
        }
        for (int i=mid;n>=i;i++)
        {
            if (i == ii)
            {
                ret = true;
                vv.push_back(v[i]);
                while (!pq.empty())
                {
                    pii p=pq.top();
                    vv.push_back(p.S);
                    pq.pop();
                }
                return true;
            }
            if (mid != 1 && p[ v[i] ].S < pq.top().F)
            {
                tot -= pq.top().F;
                pq.pop();
                pq.push(make_pair(p[ v[i] ].S,v[i]));
                tot += p[ v[i] ].S;
            }
        }
    }
    return ret;
}

int main ()
{
    scanf("%d %lld",&n,&w);
    for (int i=1;n>=i;i++)
    {
        v[i] = i;
        scanf("%lld %lld",&p[i].F,&p[i].S);
    }
    sort(v+1,v+n+1,[&](const int &a,const int &b)
     {
         return p[a].F*p[b].S < p[a].S*p[b].F;
     })
    ;
    int L=0,R=n+1;
    //L is the answer
    while (R-L != 1)
    {
        int mid=(L+R)>>1;
        if (doo(mid)) L = mid;
        else R = mid;
    }
    printf("%d\n",L);
    doo(L,true);
    for (int i:vv) printf("%d\n",i);
}