题解:
很明显的贪心题目,首先我们考虑按t2排序,因为我们先完成t2小的,那么这会比先完成t2大的留给后面人的时间更多。
但是这样会出现一个问题就是 由一个项目虽然她的t2很小,但是他的t1占用了后面太多的时间,使后面又任务不能及时完成。那么这时候我们就需要给程序填加一个反悔的功能:即当我们发现一个任务不能及时完成之后,这时其实我们可以用她和前面一个比他t1大的替换一下,那么此时我们的答案数仍然不变,但是我们的时间线确减小了。
代码:
#include<bits/stdc++.h> #define ls rt<<1 #define rs rt<<1|1 #define fi first #define se second #define pb push_back #define DEBUG(x) std::cerr << #x << '=' << x << std::endl using namespace std; typedef long long ll; typedef vector<int> VI; typedef pair<int,int> pii; typedef pair<ll,ll> pll; const ll inf = 0x3f3f3f3f3f3f3f3f; const int mod = 1e9+7; const int maxn = 2e6 + 4; const int N = 5e3 + 5; const double eps = 1e-6; const double pi = acos(-1); ll qpow(ll x,ll y){ll ans=1;x%=mod;while(y){ if(y&1) ans=ans*x%mod; x=x*x%mod; y>>=1;}return ans;} struct node{ ll t1,t2; }a[maxn]; bool cmp(node a,node b){ return a.t2<b.t2; } int n; ll now,ans; priority_queue<ll>q; int main(){ //freopen("input.in","r",stdin); scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%lld%lld",&a[i].t1,&a[i].t2); } sort(a+1,a+1+n,cmp); ll now=0; for(int i=1;i<=n;i++) { if(now+a[i].t1<=a[i].t2) { ans++; q.push(a[i].t1); now+=a[i].t1; } else { ll top=q.top();q.pop(); q.push(min(a[i].t1,top)); now-=max(0*1ll,top-a[i].t1); } } printf("%lld\n",ans); }