uvalive3635pie

关键词：

https://vjudge.net/problem/UVALive-3635

题意：

有F+1个人要分n个蛋糕，他们得到的蛋糕的面积必须是一样的，但是每个蛋糕必须是整块的蛋糕，而不是有多块蛋糕拼成的，蛋糕的形状也可以不相同。

给出n块蛋糕各自的半径，求他们每个人能得到的蛋糕的最大面积。

思路：

使得最小值最大，那显然是二分。

二分半径，计算面积，然后枚举每个蛋糕，计算每个蛋糕可以分出来的当前面积的蛋糕会有多少个，总数是否大于等于F+1即可。

记住计算个数的时候要用floor向下取整函数，而且l从0开始枚举（因为人数可能比蛋糕个数多），r从半径的最大值开始枚举就行了。

代码：

 1 #include <stdio.h>
 2 #include <math.h>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 const double pi = acos(-1.0);
 7 
 8 int a[10005];
 9 int n,f;
10 
11 bool meet(double r)
12 {
13     double area = pi * r * r;
14 
15     long long sum = 0;
16 
17     for (int i = 0;i < n;i++)
18     {
19         double one = pi * a[i] * a[i];
20 
21         sum += (int)floor(one / area);
22 
23         //printf("%f %f %d
",one,area,(int)floor(one / area));
24     }
25 
26     return sum >= f;
27 }
28 
29 int main()
30 {
31     int t;
32 
33     scanf("%d",&t);
34 
35     while (t--)
36     {
37         scanf("%d%d",&n,&f);
38 
39         f++;
40 
41         int maxn = -1;
42 
43         for (int i = 0;i < n;i++)
44         {
45             scanf("%d",&a[i]);
46 
47             maxn = max(a[i],maxn);
48         }
49 
50 
51         sort(a,a+n);
52 
53         double l = 0,r = maxn;
54 
55         for (int i = 0;i < 100;i++)
56         {
57             double mid = (l + r) / 2;
58 
59             if (meet(mid)) l = mid;
60             else r = mid;
61         }
62 
63         printf("%.5lf
",l * pi * l);
64     }
65 
66     return 0;
67 }

la3635pie(二分法)

链接：http://vjudge.net/problem/33697分析：二分答案。假设每个人得到派的最大面积是x，判断是否能满足F+1个人（因为派是不可以拼起来的，所以一个半径为r的派只能切出[πr²/x]个派，其他部分就浪费了）。1#include<cstdio>2#in... 查看详情

poj3635fulltank?

FullTank?TimeLimit:1000MS MemoryLimit:65536KTotalSubmissions:7543 Accepted:2444DescriptionAftergoingthroughthereceiptsfromyourcartripthroughEuropethissummer,yourealisedthatthegaspricesvaried 查看详情

hdu3635dragonballs（带权并查集）

题目链接：　　http://acm.hdu.edu.cn/showproblem.php?pid=3635题目描述：DragonBallsProblemDescriptionFivehundredyearslater,thenumberofdragonballswillincreaseunexpectedly,soit‘stoodifficultforMonkeyKing(WuKong)togat 查看详情

poj3635优先队列+打标记+广搜

AftergoingthroughthereceiptsfromyourcartripthroughEuropethissummer,yourealisedthatthegaspricesvariedbetweenthecitiesyouvisited.Maybeyoucouldhavesavedsomemoneyifyouwereabitmorecleveraboutwhereyoufilled 查看详情

hdu3635dragonballs

DragonBallsTimeLimit:2000/1000MS(Java/Others)    MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):4165    AcceptedSubmission(s):1603ProblemDescriptionFiv 查看详情

hdu3635

题目链接：HDU-36351#include<cstdio>2#include<cstring>3constintmaxn=10010;4intf[maxn],ct[maxn],trans[maxn];5intn,m;6voidinit()7{8for(inti=0;i<=n;i++)9{10f[i]=i;11ct[i]=1;12trans[i]=0;13}14}15 查看详情

hdu3635dragonballs(带权并查集)

题目地址：pid=3635">HDU3635加权并查集水题。用num数组维护该城市有多少龙珠，用times数组维护每一个龙珠运输了多少次。num数组在合并的时候维护。times数组因为每一个都不一样。所以要在找根的时候递归来所有维护。终于，x龙... 查看详情

hdu3635dragonballs(并查集)

DragonBallsTimeLimit:2000/1000ms(Java/Other)   MemoryLimit:32768/32768K(Java/Other)TotalSubmission(s):64   AcceptedSubmission(s):26Font: TimesNewRoman | Ve 查看详情

la3635派

题目链接：https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1636题意：f+1个人，来分n个圆形派，每个人只能从一个派中拿，也就是说，不能从两个里面去拼。求每个人最大的面积。分析：二... 查看详情

poj3635fulltank?[分层图最短路]

FullTank?TimeLimit: 1000MS MemoryLimit: 65536KTotalSubmissions: 7248 Accepted: 2338DescriptionAftergoingthroughthereceiptsfromyourcartripthroughEuropethissummer,yourealis 查看详情

图论补完计划poj3635（最短路变形）

FullTank?TimeLimit:1000MS MemoryLimit:65536KTotalSubmissions:7427 Accepted:2399DescriptionAftergoingthroughthereceiptsfromyourcartripthroughEuropethissummer,yourealisedthatthegaspricesvaried 查看详情

hdu3635(代码片段)

/*一开始第a个球在第a个城市操作Tab，把第a个球所在城市的所有球移到b所在的城市操作Qa要求输出第a个球在哪个城市第a个球所在的城市有几个球第a个球移动次数*/#include<iostream>#include<cstring>#include<cstdio>#definemovemovee#... 查看详情

ob3635/ob2530pap/ob3398昂宝电子设计

OB3635MCPA 4-7X1W过认证 //QQ2892715427//输入电压：100-264VAC输入电流：＜0.1APF ＞0.5输出电压：12-25V输出电流：0.26-0.3A空载电压：＜40V 空载功率:＜0.1W 恒流精度： ±5%效率： ＞88% 启动时间：＜1S 耐压：... 查看详情

昂宝ob3635ampob33398mp大功率投光灯80w驱动照明

 昂宝OB3635AMP、OB33398MP大功率投光灯80W驱动照明、QQ 2892715427 InputCharacteristics ACinputvoltagerating100Vac~240Vac ACinputvoltagerange90Vac~264Vac ACinputfrequencyrange47Hz~63Hz1.2 查看详情

hdu3635dragonballs（带权并查集）(代码片段)

DragonBallsTimeLimit:2000/1000MS(Java/Others)    MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):10628    AcceptedSubmission(s):3802ProblemDescriptionFivehundredyearslater,thenumberofdragonballswillincreaseunexpectedly,soit‘stoodifficultforMonkeyKing... 查看详情

zoj-3635cinemainakiba（树状数组+二分）

题意：已知有n个人，从第一个人开始每个人被安排在第ai个空座上，有m组询问，问某人所坐的位置。分析：1、用树状数组维护空座的个数，方法：将所有的空座初始化为1，sum（x）则表示从座位1到座位x空座的个数。2、对于每... 查看详情

hdu-3635dragonballs并查集(代码片段)

题意：1~N个龙珠，放在1~N个城市，有两种操作：TAB将A所再城市的所有球转移到B所在的城市。QX询问X所在的城市pls，该城市中龙珠数量nm，以及龙珠转移次数trs题解：并查集模板题，顺带更新一些数据。pls不必更新，因为X所在的... 查看详情

poj3635fulltank?(代码片段)

【题解】    用dijkstra算法求最短路。同时考虑在每个节点加油（一单位）与否。【代码】1#include<iostream>2#include<map>3#include<cstring>4#include<string>5#include<queue>6usingnamespacestd;7#definemaxn10058#definemaxm10... 查看详情