比赛 |
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;
- }