链接

[]

题意

给你n个题目，考试时间T，对于每个问题都有一个ai，以及解决所花的时间，

让你找到一个做题（选择k个题去做）的方案,使得最后ai<=k的情况最多

分析

其实我刚开始不会的，后来看大佬的才会的

我们先利用vector数组根据ai大小分类，然后对于每一类肯定是时间少的有限考虑，所以考虑用优先队列。

那么我们只要去由n到0枚举即可。

先把ai为i的题目入队列，然后如果此时队列里的题目数大于i的话，我们需要把时间大的出队列即可(因为队列中的题目ai一定大于等于i，删去哪个都一样)。

过程中统计总时间sum确保不超过T即可。

然后再枚举的过程中只要q.size()==i&&sum<=T即满足条件。

具体看代码吧

代码

#include
    
     using namespace std;#define ll long longconst int maxn=2e5+10;vector
     
      
        > v[maxn];priority_queue
       
        
          > q;//优先队列默认最大堆 int n,T;int main(){    ios::sync_with_stdio(false);    cin.tie(0);    cout.tie(0);        int a,c,i;    //freopen("in.txt","r",stdin);    cin>>n>>T;    for(i=1;i<=n;i++)    {        cin>>a>>c;        v[a].push_back(make_pair(c,i));//把ai一样的存在一起     }        ll sum=0;    for(i=n;i>=0;i--){        for(auto u:v[i]){            q.push(u);            sum+=u.first;        }                while(q.size()>i){            sum-=q.top().first;            q.pop();//把最耗时的出队         }                if(q.size()==i&&sum<=T){//贪得最大满足条件，因为往后i--不可能比现在大了             cout<
         <<' '<<