LA3635派

【LA3635】

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=456&page=show_problem&problem=3249

【题目描述】:

你和你的F个小伙伴，排排左，分n个半径不同的圆形pie，要求每个人必须分到整块（类扇形），每个人分的面积相同，目标是这个面积最大。

【解题思路】：

运筹三要素分析

【决策方案】:

在[0,max]的线性离散区间上连续选择面积

【约束条件】：

A：每个人都要分到一个扇形的整的pie

【目标评判标准】：

B：选择的面积是最大的

在上面分析的方案中，通过A可剔除一部分，通过B确定最优解；

【算法分析】：

备选答案是线性分布的即｛0......max｝都可能是最优解，而且满足单调性原则，所以可以二分枚举结果；这道题还有一个关键之处，pie是可以任意分割的，可以得到我们想得到的任意大小。

PS：这道题目分析方案比较难

【代码分析】：

主体是二分部分，本来以为比较难写，但是加了eps后发现，连区间的边界的更新都不需要考虑了。｛也许以后写离散二分的时候可以放缩成小数｝

【完整代码】：

  1 #include<iostream>
  2 
  3 #include<stdio.h>
  4 
  5 #include<string.h>
  6 
  7 #include<algorithm>
  8 
  9 #include<stdlib.h>
 10 
 11 #include<math.h>
 12 
 13 #include<queue>
 14 
 15 #include<vector>
 16 
 17 #include<map>
 18 
 19 #define MAXN 10000+5
 20 
 21 #define MAXM 20000+5
 22 
 23 #define oo 9556531
 24 
 25 #define eps 0.000001
 26 
 27 #define PI acos(-1.0)//这个精确度高一些
 28 
 29 using namespace std;
 30 
 31 double a[MAXN];
 32 
 33 int cas,n,f;
 34 
 35 bool isok(double s)
 36 
 37 {
 38 
 39     int aimp=0;//在分的面积是s的情况下，最多能分几个人
 40 
 41     for(int i=0;i<n;i++)
 42 
 43     aimp+=(int)(a[i]/s);
 44 
 45     if (aimp>=f+1) return true;else return false;
 46 
 47 }
 48 
 49 double absdou(double x)
 50 
 51 {
 52 
 53     if (x>=0) return x;else return -x;
 54 
 55 }
 56 
 57 int main()
 58 
 59 {
 60 
 61  
 62 
 63     cin>>cas;
 64 
 65     for(;cas;cas--)
 66 
 67     {
 68 
 69         cin>>n>>f;
 70 
 71         double l=0,r=0;
 72 
 73         for(int i=0;i<n;i++) {
 74 
 75             cin>>a[i];
 76 
 77             a[i]=a[i]*a[i]*PI;
 78 
 79             if (a[i]>r) r=a[i];//最大是一个整的pie
 80 
 81         }
 82 
 83         r=r+1;
 84 
 85         while(absdou(r-l)>eps)
 86 
 87         {
 88 
 89             double m=(l+r)/2;
 90 
 91             if (isok(m)) l=m;else r=m;
 92 
 93         }
 94 
 95         printf("%.4f
",l);
 96 
 97     }
 98 
 99     return 0;
100 
101 }

【关键词】：读题，二分