比赛 20160415 评测结果 AEEEEAEEEA
题目名称 烤鸡翅 最终得分 30
用户昵称 WAHT 运行时间 1.462 s
代码语言 C++ 内存使用 4.89 MiB
提交时间 2016-04-15 09:13:11
显示代码纯文本
  1. #include<iostream>
  2. #include<cstdio>
  3. #include<algorithm>
  4. #include<cstring>
  5. #include<queue>
  6. #define ll long long
  7. using namespace std;
  8. const int maxn=300000;
  9. ll read()
  10. {
  11. ll x=0;
  12. char ch=getchar();
  13. while(ch>'9'||ch<'0') ch=getchar();
  14. while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
  15. return x;
  16. }
  17. int n;
  18. ll x[maxn],y[maxn];
  19. priority_queue<ll>q;
  20. bool check(int a)
  21. {
  22. while(!q.empty()) q.pop();
  23. ll sum=0,num=0;;
  24. for(int i=1;i<=n;i++)
  25. {
  26. sum+=x[i];
  27. if(sum>=y[i])
  28. {
  29. q.push(y[i]);
  30. sum-=y[i];
  31. num++;
  32. if(num==a) return true;
  33. }
  34. else if(q.top()>y[i])
  35. {
  36. sum+=q.top()-y[i];
  37. q.pop();
  38. q.push(y[i]);
  39. }
  40. }
  41. return false;
  42. }
  43. int main()
  44. {
  45. freopen("wing.in","r",stdin);
  46. freopen("wing.out","w",stdout);
  47. n=read();
  48. for(int i=1;i<=n;i++) x[i]=read();
  49. for(int i=1;i<=n;i++) y[i]=read();
  50. int l=0,r=n;
  51. while(l+1<r)
  52. {
  53. int mid=l+r>>1;
  54. if(check(mid)) l=mid;
  55. else r=mid;
  56. }
  57. if(check(r)) cout<<r<<endl;
  58. else cout<<l<<endl;
  59. return 0;
  60. }