题目

传送门

思路

注意到一个细节，每一个题最多产生1的贡献，所以若要得到k分，至少要做k道题

这样就能\(O(n)\)的判断能否得到k分

二分k就行了

代码

#include<iostream>
#include<algorithm>
using namespace std;
struct node
{
    int id;
    int a;
    int t;
    friend bool operator < (const node &a,const node &b)
    {
        return a.t<b.t;
    }
}a[200005];
int n;
long long t;
long long l;
long long r;
long long mid;
vector<int> ans;
bool check(long long cnt)
{
    long long ret=0;
    int tot=0;
    vector<int> v;
    for(int i=1;i<=n;i++)
    {
        if(a[i].a>=cnt)
        {
            ret+=a[i].t;
            tot++;
            v.push_back(a[i].id);
        }
        if(tot==cnt)
            break;
    }
    if(tot<cnt)
        return 0;
    if(ret<=t)
    {
        ans=v;
        return 1;
    }
    return 0;
}
int main()
{
    cin>>n>>t;
    for(int i=1;i<=n;i++)
    {
        a[i].id=i;
        cin>>a[i].a>>a[i].t;
    }
    sort(a+1,a+n+1);
    l=0;
    r=n;
    while(l+1<r)
    {
        mid=(l+r)>>1;
        if(check(mid))
            l=mid;
        else
            r=mid;
    }
    while(check(l+1))
        l++;
    cout<<l<<'\n'<<ans.size()<<'\n';
    for(int i=0;i<ans.size();i++)
        cout<<ans[i]<<' ';
    return 0;
}

习题：Too Easy Problems （二分）

原文：https://www.cnblogs.com/loney-s/p/12269506.html