贪心,每次如果够直接卖,不够找到之前的卖出的最多的一份,然后反悔
不过反悔的确是很好的策略!
#include#include #include #include #include #include #define N 250005using namespace std;priority_queue q;long long n,a[N],b[N],ans,now;int main(){ freopen("wing.in","r",stdin); freopen("wing.out","w",stdout); scanf("%lld",&n); for(int i=1;i<=n;i++) scanf("%lld",&a[i]); for(int i=1;i<=n;i++) scanf("%lld",&b[i]); for(int i=1;i<=n;i++){ now+=a[i]; if(now>=b[i]){ now-=b[i]; q.push(b[i]); ans++; } else if(!q.empty()&&q.top()>b[i]){ now+=q.top(); now-=b[i]; q.pop(); q.push(b[i]); } } printf("%lld\n",ans); return 0;}