Pie Cable master 两道类似的二分题-白红宇的个人博客

发布日期：2021-05-07 16:48:52 浏览次数：26 分类：技术文章

本文共 1238 字，大约阅读时间需要 4 分钟。

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        using namespace std;#define pi acos(-1.0)double a[10010];int main(){   	int t;	double l,r;	double mid;	scanf("%d",&t);	while(t--){   		memset(a,0,sizeof(a));		int n;		int f;		scanf("%d%d",&n,&f);		double Max=0;		for(int i=0;i
        
         0.0000001){ mid=(r+l)/2; int sum=0; for(int i=0;i
         
          f) l=mid; else r=mid; } printf("%.4lf\n",mid); } return 0;}

题目大意多组输入，每组，n，f，n个饼f个人分，饼可以切开，形状随意，体积相同就行，输出每个人可以分到的最大的体积。

问题分析，我们在存数组的时候同时求出饼的体积，找到最大的那个。声明两个指针，左和右，饼的体积是没有排序的，每次遍历一遍，(int)强制转换使得一共有两种状态，非零即一，sum记录的是大于mid的答案，(mid不是中位数，只是相当于一个指针，确定能取的饼的最大体积），如果大于f的个数，说明mid足够小，就把左指针移动到mid的位置，将想取得的体积(mid)变大，反之，说明mid足够大…

有大于f个体积 V 的 a[i] (第i个饼的体积) 是解题的关键，剩下的思想是寻找合适的V,通过移动l，r确定V在(0~Max)中的值，此处的V,就是代码中出现的mid。

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              using namespace std;const int maxn=1010;const int INF=0x3f3f3f3f;double a[10005];int main(){ int n,k; double l,r; double mid; while(~scanf("%d%d",&n,&k)){ double Max=-1; if(n==0&&k==0) break; for(int i=0;i
              
               =k) l=mid; else r=mid; } printf("%.2lf\n",mid); } return 0;}

上一篇：刷题计划1——poj1753

下一篇：Find a multiple

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章