[关闭]
@zzzc18 2017-09-24T08:54:19.000000Z 字数 1258 阅读 1238

2017.09.23 平均数

TEST


题目:

image_1bqph7c7c1q4pku5753fc413kpm.png-88.6kB
image_1bqph858g16c61s38baqmmg1sep13.png-32.8kB

Solution:

image_1bqph57611npi1mvr1ate1mtm18et9.png-79.9kB

丧心病狂的出题人连BIT逆续对都要卡
注意由于是对前缀和求逆续对,所以归并排序应该是 的S


  1. #include<cstdio>
  2. #include<climits>
  3. #include<cstring>
  4. #include<algorithm>
  5. using namespace std;
  6. typedef long long LL;
  7. const int MAXN = 100000+9;
  8. int n;
  9. LL k;
  10. int num[MAXN];
  11. double num2[MAXN];
  12. double s[MAXN];
  13. double tmp[MAXN];
  14. LL tot=0;
  15. int L,R;
  16. void merge_sort(double A2[],int l,int r,double A1[]){
  17. if(l==r)
  18. return;
  19. int mid=(l+r)>>1;
  20. merge_sort(A2,l,mid,A1);
  21. merge_sort(A2,mid+1,r,A1);
  22. int q1=l,q2=mid+1;
  23. int cnt=l;
  24. while(q1<=mid && q2<=r){
  25. if(A1[q1]<A1[q2])
  26. A2[cnt++]=A1[q1++];
  27. else{
  28. A2[cnt++]=A1[q2++];
  29. tot+=mid-q1+1;
  30. }
  31. }
  32. while(q1<=mid) A2[cnt++]=A1[q1++];
  33. while(q2<=r) A2[cnt++]=A1[q2++];
  34. for(int i=l;i<=r;i++) A1[i]=A2[i];
  35. }
  36. void mergesort(int l,int r,double A[]){
  37. merge_sort(tmp,l,r,A);
  38. }
  39. void OUT(){
  40. int i;
  41. for(i=1;i<=n;i++)
  42. printf("%.4lf ",s[i]);
  43. puts("");
  44. }
  45. bool work(double x){
  46. int i;
  47. for(i=1;i<=n;i++) num2[i]=num[i]*1.0-x;
  48. for(i=1;i<=n;i++) s[i]=s[i-1]+num2[i];
  49. tot=0;
  50. mergesort(0,n,s);
  51. //OUT();
  52. //printf("%.4lf %lld\n",x,tot);
  53. return tot>=k;
  54. }
  55. void solve(){
  56. double l=L*1.0,r=R*1.0;
  57. while(r-l>=0.00001){
  58. double mid=(l+r)/2;
  59. if(work(mid))
  60. r=mid;
  61. else
  62. l=mid;
  63. }
  64. printf("%.4lf\n",l);
  65. }
  66. int main(){
  67. freopen("ave.in","r",stdin);
  68. freopen("ave.out","w",stdout);
  69. scanf("%d%lld",&n,&k);
  70. int i;
  71. L=INT_MAX;R=INT_MIN;
  72. for(i=1;i<=n;i++){
  73. scanf("%d",&num[i]);
  74. L=min(L,num[i]);
  75. R=max(R,num[i]);
  76. }
  77. solve();
  78. return 0;
  79. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注