题目描述 Description OI教练BG在n天中每天早晨会给wxjlzbcd发一套题，其中包含A_i道题目。如果不做的话，题目会累加到下一天。 wxjlzbcd每天能够刷掉的题目数量为B_i，BG的题目数量太少，可能不能满足wxjlzbcd每天刷题的需求，如果题目数量不够，wxjlzbcd当天就不会刷题，因为空出来的时间他有可能会浪费掉。
但是wxjlzbcd不想天天颓废，他想知道自己最多能有多少天有题刷。 输入输出格式 Input/output 输入格式： 输入第1行为一个整数n，表示天数。 第2行包括n个数字A_i，表示BG n天中每天发的题目数A_i。 第3行包括n个数字B_i，表示wxjlzbcd n天中每天能刷掉的题目数B_i。 输出格式： 输出第1行为一个整数ans，表示天数。 输入输出样例 Sample input/output 样例测试点#1 输入样例： 5 1 4 1 2 3 1 2 3 4 5 输出样例： 4 说明 description 对于40%的数据，保证1≤n≤1000； 对于100%的数据，保证1≤n≤250000，0≤a_i≤10^9，0≤b_i≤10^9。
这个题要用到贪心算法，一般做法就是从前往后找，如果当天总共题目数能满足当天要求就继续向后，如果不行就找前面用过的消耗题目数最多的一天，如果之前选出的这一天不做题后能够满足现在这一天的要求的话，就将这一天取消。 如果不用根堆的话只能得60分。代码（60）：
#include<iostream> #include<algorithm> #include<deque> #include<cstring> using namespace std; int i,j,h,n,m,maxx,ma; int temp,a[250001],t; int b[250001],c[250001]; int r() { int ans=0; char ch=getchar(); while(ch<'0'||ch>'9') { ch=getchar(); } while(ch>='0'&&ch<='9') { ans*=10; ans+=ch-'0'; ch=getchar(); } return ans; } int main() { freopen("prob.in","r",stdin); freopen("prob.out","w",stdout); n=r(); for(i=1;i<=n;i++) a[i]=r(); for(i=1;i<=n;i++) { c[i]=r(),maxx=0; temp+=a[i]; if(temp>=c[i]) t++,temp-=c[i],b[i]=1; else {for(j=1;j<i;j++) if(c[j]>c[i]&&maxx<c[j]&&b[j]) maxx=c[j],ma=j; if(maxx) temp+=c[ma],temp-=c[i],b[ma]=0,b[i]=1;} } cout<<t; return 0; }用了C++STL之后就是这样：代码（100）
#include<cstdio> #include<cctype> #include<cstdlib> #include<queue> #include<iostream> #include<algorithm> using namespace std; int i,j,n,m; int a[250001]; long long temp; int b[250001],c[250001]; int r() { int ans=0; char ch=getchar(); while(ch<'0'||ch>'9') { ch=getchar(); } while(ch>='0'&&ch<='9') { ans*=10; ans+=ch-'0'; ch=getchar(); } return ans; } priority_queue<pair<int,int> >q; int main() { freopen("prob.in","r",stdin); freopen("prob.out","w",stdout); n=r(); for(i=1;i<=n;i++) a[i]=r(); for(i=1;i<=n;i++) c[i]=r(); for(i=1;i<=n;i++) { temp+=a[i]; if(temp>=c[i]) { q.push(make_pair(c[i],i)); temp-=c[i]; b[i]=1; } else if(!q.empty()&&c[i]<q.top().first) { b[q.top().second]=0; temp+=q.top().first; q.pop(); temp-=c[i]; q.push(make_pair(c[i],i)); b[i]=1; } } cout<<q.size(); return 0; }