比赛 20160415 评测结果 AEEEEAEEEA
题目名称 烤鸡翅 最终得分 30
用户昵称 WAHT 运行时间 1.462 s
代码语言 C++ 内存使用 4.89 MiB
提交时间 2016-04-15 09:13:11
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define ll long long
using namespace std;
const int maxn=300000;
ll read()
{
	ll x=0;
	char ch=getchar();
	while(ch>'9'||ch<'0')	ch=getchar();
	while(ch>='0'&&ch<='9')	x=x*10+ch-'0',ch=getchar();
	return x;
}
int n;
ll x[maxn],y[maxn];
priority_queue<ll>q;
bool check(int a)
{
	while(!q.empty())	q.pop();
	ll sum=0,num=0;;
	for(int i=1;i<=n;i++)
	{
		sum+=x[i];
		if(sum>=y[i])
		{
			q.push(y[i]);
			sum-=y[i];
			num++;
			if(num==a)	return true;
		}
		else	if(q.top()>y[i])
		{
			
			sum+=q.top()-y[i];
			q.pop();
			q.push(y[i]);
		}
	}
	return false;
}
int main()
{
	freopen("wing.in","r",stdin);
	freopen("wing.out","w",stdout);
	n=read();
	for(int i=1;i<=n;i++)	x[i]=read();
	for(int i=1;i<=n;i++)	y[i]=read();
	
	int l=0,r=n;
	while(l+1<r)
	{
		int mid=l+r>>1;
		if(check(mid))	l=mid;
		else r=mid;	
	}
	if(check(r))	cout<<r<<endl;
	else cout<<l<<endl;
	return 0;
}