パイ(c++)

11330 ワード

パイ(c++)
タイトル
私の誕生日が来ます!習慣によって、私はいくつかのパイをみんなに分ける必要があります.私はN個の異なる味、異なる大きさのパイを持っています.F人の友达が私のパーティーに来て、一人一人が1つの派を手に入れます(1つの派の1つが必要で、いくつかの派の小さい塊からつづることができません;1つの派全体です).
私の友达はとてもけちで、もし誰かがもっと大きなものを手に入れたら、文句を言い始めます.だから全員が手に入れたパイは同じ大きさ(同じ形をする必要はありません)で、無駄にされる派もありますが、パーティー全体を壊すよりはましです.もちろん、私も自分に1枚残して、この1枚も他の人と同じ大きさにします.
すみません、私たち一人一人が手に入れたパイは最大いくらですか?各パイは1つの高さ、半径の異なる円柱です.
入力
第1行は2つの正の整数NとFを含み、1≦N、F≦10,000は、派の数と友达の数を表す.2行目は、各パイの半径を表すN個の1〜10000の整数を含む.
しゅつりょく
各人が得ることができる最大の派の体積を出力し、小数点以下の3桁まで正確にします.
サンプル入力
3 3 4 3 3
サンプル出力
25.133
問題を解く構想.
各派閥の体積を求めて並べ替え,まず適当な大きさの派閥の体積を仮定する.各パイの体積でこのパイの体積を除去し、どれだけのブロックに分けることができるかを求めます.ブロック数が少なければ、パイの体積が大きくなったことを示します.このとき、区間を二分法で左に移動し、逆に右に移動して、左値と右値の距離が十分に小さいまで移動します.この时、パイの体積は左の値を取って、小さい体積のため、きっと十分に分けます.
コード#コード#
#include 
#include 
#include 
#include 
using namespace std;
#define pi 3.141592653589
#define maxn 10010
int n,person,i;
int flag = 0;
double sum = 0;
double l,r,mid;
double a[maxn];
double v[maxn];
int find(double m,int person,int n,double v[]);
int main() 
{
 
	cin >> n >> person;
	person++;//    
 
	for(i = 0; i < n; i++)
		cin >> a[i];//    
 
	for(i = 0; i < n; i++) 
    {
		v[i] = pi*a[i]*a[i];//      ,  1
		sum += v[i];//    									 
	}
 
	sort(v,v+n);//                                       
 
	l = 0;//   0
	r = v[n-1];//         
	mid = l - (l-r)/2;//    
	while (r-l > 1e-5)//l r     1 -5   ,          
    {
		if (find(mid,person,n,v)) //        ,           
        {
			r = mid;
			mid = l  - (l-r)/2;
		} 
        else 
        {
			l = mid;//    ,        
			mid = l - (l-r)/2;
		}
	}
    printf("%.3f
"
,l); return 0; } int find(double m,int person,int n,double v[]) { int number = 0;// for (int i = n-1; i >= 0; i --) { number += (v[i]/m);// , } if (number < person) return 1;// , 。 else return 0;// , 。 }