パイ(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
問題を解く構想.
各派閥の体積を求めて並べ替え,まず適当な大きさの派閥の体積を仮定する.各パイの体積でこのパイの体積を除去し、どれだけのブロックに分けることができるかを求めます.ブロック数が少なければ、パイの体積が大きくなったことを示します.このとき、区間を二分法で左に移動し、逆に右に移動して、左値と右値の距離が十分に小さいまで移動します.この时、パイの体積は左の値を取って、小さい体積のため、きっと十分に分けます.
コード#コード#
タイトル
私の誕生日が来ます!習慣によって、私はいくつかのパイをみんなに分ける必要があります.私は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;// , 。
}