le-interchange-newline">
6650Falling Ants
Ants make up 10% of the total world animal tissue. The
total biomass of all the ants on Earth is roughly equal to the
total biomass of all the p eople on Earth. However, unlike
the p eople on Earth when they fall from a height they do
not die for two reasons:
•They have so little mass relative to their air resistance
that they fall slowly and, therefore, have little energy
to dissipate when they hit the ground.
•Their b o dies are tiny deformable tanks, well designed
to absorb blows.
In general, small ob jects have less impact of gravitation
on them b ecause they have more surface area/volume compared to larger ob jects. For example consider
a (1x1x1) cub e. Its surface area is 6 and volume is 1. So the ratio is 6:1 and for a (10x10x10) cub e the
surface area is 600 and volume is 1000. So the ratio is 6:10. Given the shap e of many ants you will
have to find out which ant has the highest effect of gravitation on it.
For simplicity we will assume the following things in this
problem:
1. All ants are described as a box shaped object. A box
shaped object is described with three integersL,W,
andH which denotes the length, width and height of
the object. So the volume of the ant is (L ×W×H).
2. The density (Mass per unit volume) is 1. So the mass
of the above mentioned ant is also (L ×W×H) and so
the weight is (L ×W×H)× g(Hereg is the acceleration
caused by gravitation).
3. When an ant freely falls four sides are upright and
so the faces at the top and bottom are parallel with
the horizon. So the area of the plane facing bottom
is alwaysL ×W. For any ant the upward force put
by the air is proportional to the area of the of the
bottom face. To be specific it isL ×W2× g. After some
manipulation it can be proved that the downward accelerationf =g −2gH. So the downward acceleration actually depends solely on the value of H
(asg is same for all ants).
Given the dimension of several ants, report the volume of the ant that has the highest downward
acceleration. If there is a tie, report the one with the largest volume.
Universidad de Valladolid OJ:6650 – Fal ling Ants 2/2
Input
The input file contains at most 500 test cases. The description of each test case is given below:
First line of each test case contains an integerT (T ≤100) which denotes the total number of ants
to consider. Each of the nextT lines contains three integers which denote the value ofL,W andH
(1≤ L, W, H≤50) of an ant respectively.
Input is terminated by a line containing a single zero.
Output
For each set of input produce one line of output. This line contains the volume of the ant that has the
highest downward acceleration. If there is a tie report the ant with the highest volume.
Sample Input
3
3 4 5
12 1 5
20 10 4
3
3 4 5
20 30 5
1 2 4
0
Sample Output
60
然而最简单的方法也是更优美的解法应该是用类似在线算法的做法
简单易懂又简洁明了.
Ants make up 10% of the total world animal tissue. The
total biomass of all the ants on Earth is roughly equal to the
total biomass of all the p eople on Earth. However, unlike
the p eople on Earth when they fall from a height they do
not die for two reasons:
•They have so little mass relative to their air resistance
that they fall slowly and, therefore, have little energy
to dissipate when they hit the ground.
•Their b o dies are tiny deformable tanks, well designed
to absorb blows.
In general, small ob jects have less impact of gravitation
on them b ecause they have more surface area/volume compared to larger ob jects. For example consider
a (1x1x1) cub e. Its surface area is 6 and volume is 1. So the ratio is 6:1 and for a (10x10x10) cub e the
surface area is 600 and volume is 1000. So the ratio is 6:10. Given the shap e of many ants you will
have to find out which ant has the highest effect of gravitation on it.
For simplicity we will assume the following things in this
problem:
1. All ants are described as a box shaped object. A box
shaped object is described with three integersL,W,
andH which denotes the length, width and height of
the object. So the volume of the ant is (L ×W×H).
2. The density (Mass per unit volume) is 1. So the mass
of the above mentioned ant is also (L ×W×H) and so
the weight is (L ×W×H)× g(Hereg is the acceleration
caused by gravitation).
3. When an ant freely falls four sides are upright and
so the faces at the top and bottom are parallel with
the horizon. So the area of the plane facing bottom
is alwaysL ×W. For any ant the upward force put
by the air is proportional to the area of the of the
bottom face. To be specific it isL ×W2× g. After some
manipulation it can be proved that the downward accelerationf =g −2gH. So the downward acceleration actually depends solely on the value of H
(asg is same for all ants).
Given the dimension of several ants, report the volume of the ant that has the highest downward
acceleration. If there is a tie, report the one with the largest volume.
Universidad de Valladolid OJ:6650 – Fal ling Ants 2/2
Input
The input file contains at most 500 test cases. The description of each test case is given below:
First line of each test case contains an integerT (T ≤100) which denotes the total number of ants
to consider. Each of the nextT lines contains three integers which denote the value ofL,W andH
(1≤ L, W, H≤50) of an ant respectively.
Input is terminated by a line containing a single zero.
Output
For each set of input produce one line of output. This line contains the volume of the ant that has the
highest downward acceleration. If there is a tie report the ant with the highest volume.
Sample Input
3
3 4 5
12 1 5
20 10 4
3
3 4 5
20 30 5
1 2 4
0
Sample Output
60
3000
这道题本来是有图的，不过有图没图都是一样的，题目的大意就是求蚂蚁下落的最大加速度，所有公式都给我们了，而且题目也规定了情况也是最好的，本来应该说是一道很水的题目，然而在水题上依然可以看出差距来，小生愚钝，用的优先队列。
#include<cstdio>
#include<algorithm>
#include <queue>
#define maxn1 105
using namespace std;
struct ants{
int l,w,h;
int v;
};
bool operator < (struct ants a,struct ants b){
if(a.h == b.h){
if(a.v < b.v)
return true;
else
return false;
}else{
if(a.h < b.h)
return true;
else
return false;
}
}
int main(){
int n;
while(scanf("%d",&n) && n){
struct ants now[maxn1];
priority_queue<struct ants> lis;
for(int i = 0;i < n;i++){
scanf("%d %d %d",&now[i].l,&now[i].w,&now[i].h);
now[i].v = now[i].h*now[i].l*now[i].w;
lis.push(now[i]);
}
struct ants t = lis.top();
printf("%d\n",t.v);
}
return 0;
}
然而最简单的方法也是更优美的解法应该是用类似在线算法的做法
#include<iostream>
using namespace std;
int main(){
int n;
while(cin>>n&&n){
int l,w,h,maxs=0,maxh=0;
for(int i=1;i<=n&&cin>>l>>w>>h;i++){
if(h>maxh){maxh=h;maxs=l*w;}
if(h==maxh&&l*w>maxs)maxs=l*w;
}
cout<<maxs*maxh<<'\n';
}
}
简单易懂又简洁明了.
![[AtCoder ARC098] Donation| 建图 | 树型dp](https://ucc.alicdn.com/pic/developer-ecology/8e5d18c9f8184827bb891d63b77aec20.png?x-oss-process=image/resize,h_160,m_lfit)