poj3122--二分加贪心

大致题意:

就是公平地分披萨pie

我生日,买了n个pie,找来f个朋友,那么总人数共f+1人

每个pie都是高为1的圆柱体,输入这n个pie的每一个尺寸(半径),如果要公平地把pie分给每一个人(就是所有人得到的pie尺寸一致,但是形状可以不同),而且每个人得到的那份pie必须是从同一个pie上得到的

后面那句很重要,

就是说如果有3个pie, 尺寸分别为1,2,3,

如果要给每人尺寸为2的pie,那么最多分给2个人,而不是3个人

因为第一个pie尺寸为1,小于2,扔掉

第二个pie尺寸为2,等于2,刚好分给一个人

第三个pie尺寸为3,切出尺寸为2的一份,分给一个人,剩下的尺寸为1的就扔掉

千万不要陷入  (1+2+3)/2=3人的误区,这样就变成求平均了

解题思路:

#include<iostream>
using namespace std;
const double PI=3.14159265359;
const double cha=1e-;
int main(){
int n,pie,man;
cin>>n;
while(n--){
cin>>pie>>man;
man++;
double max=0.0;
double *size=new double[pie+];
for(int i=;i<pie;i++){
cin>>size[i];
size[i]*=size[i];
if(size[i]>max)//把其中最大的pie求出来
max=size[i];
}
double high=max,mid,sma=0.0;
int sum;
while(high-sma>cha){
sum=;
mid=(high+sma)/;
for(int i=;i<pie;i++){
sum=sum+(int)(size[i]/mid);
}
if(sum>=man)//如果人数符合,肯定还想把pie 尽量分得大一点,故在此用等号
sma=mid;
else
high=mid;
}
printf("%.4f\n",mid*PI);
delete size;
}
return ;
}

输入的是朋友的数量f,分pie是分给所有人,包括自己在内共f+1人

下界low=0,即每人都分不到pie

上界high=maxsize,每人都得到整个pie,而且那个pie为所有pie中最大的

(上界就是 n个人n个pie,每个pie还等大)

对当前上下界折中为mid,计算"如果按照mid的尺寸分pie,能分给多少人"

求某个pie(尺寸为size)按照mid的尺寸,能够分给的人数,就直接size / mid,舍弃小数就可以

由于每个pie都是圆的,为了保证精度和减少运算,我的程序在计算过程中把 π 先忽略,仅仅用半径R²去计算,最后的结果再乘π

没难度的二分题,若果WA要多多留意是不是精度问题,因为算法思路是很明确的,精度才是最头疼的

上一篇:清除nginx静态资源缓存


下一篇:java 工作内存