D. Too Easy Problems(二分+优先队列)

$这个....很容易想到二分吧?$

$二分能获得的题目分数mid$

$每次把a_i>=mid的题目装进优先队列(可能产生贡献)$

$每次从队列中拿一个最小时间的题目来写$

正确性显然

#include <bits/stdc++.h> using namespace std; const int maxn=2e5+10; int n,T; struct p{ int q,w,num; bool operator < (const p&tmp ) const{ return this->w>tmp.w;//时间小的放后面 } }a[maxn]; vector<int>sq,sw; bool isok(int mid) { priority_queue<p>q; for(int i=1;i<=n;i++) if(a[i].q >= mid) q.push( a[i] ); int sumn_t=0,shu=0; while( !q.empty() ) { p now=q.top(); q.pop(); sumn_t += now.w,shu++; sq.push_back( now.num ); if(sumn_t>T) return false; if(shu==mid) { sw=sq; return true; } } return false; } int main() { cin >> n >> T; for(int i=1;i<=n;i++) scanf("%d%d",&a[i].q,&a[i].w),a[i].num=i; int l=1,r=n,mid; while(r>=l) { mid = l+r>>1; if( isok(mid) ) l=mid+1; else r=mid-1; sq.clear(); } cout<<sw.size()<<endl; cout<<sw.size()<<endl; for(int i=0;i<sw.size();i++) cout<<sw[i]<<" "; }

其实还有直接贪心的

$这个贪心算是带反悔的贪心吧$

$先按照时间小到大排序,一直往后选并扔进队列$

$每次加入一题后,如果选的题目数大于当前a_i最小的$

$就弹出那个不符合条件且耗时最大的题目$