[关闭]
@lychee123 2017-02-26T03:52:10.000000Z 字数 1086 阅读 925

HDU:5432—Pyramid Split(二分)

二分

题面链接

  1. #include<stdio.h>
  2. #include<map>
  3. #include<algorithm>
  4. #include<string.h>
  5. using namespace std;
  6. double a[10010],b[10010];
  7. double v1,v2,maxh;
  8. int main()
  9. {
  10. int t,n,i;
  11. scanf("%d",&t);
  12. while(t--)
  13. {
  14. maxh=-1;
  15. v1=0;
  16. scanf("%d",&n);
  17. for(i=0;i<n;i++)
  18. {
  19. scanf("%lf",&a[i]);
  20. maxh=max(maxh,a[i]);
  21. }
  22. for(i=0;i<n;i++)
  23. scanf("%lf",&b[i]);
  24. for(i=0;i<n;i++)
  25. v1+=a[i]*b[i]*b[i];
  26. v1/=6;
  27. double l=0,r=maxh,v2,wide,mid;
  28. while(r-l>0.0001)
  29. {
  30. mid=(l+r)/2;
  31. v2=0;
  32. for(i=0;i<n;i++)
  33. {
  34. if(a[i]<=mid)
  35. continue;
  36. wide=(a[i]-mid)/a[i]*b[i];
  37. v2+=wide*wide*(a[i]-mid)/3;
  38. }
  39. if(v2>v1)
  40. l=mid;
  41. else
  42. r=mid;
  43. }
  44. printf("%d\n",(int)l);
  45. }
  46. return 0;
  47. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注