JAVA The Task A small group of biologists plan to research the spread of a contagious disease infecting seaweed and publ

[answerhappygod]

JAVA
The Task
A small group of biologists plan to research the spread of a
contagious disease infecting seaweed and publish their findings in
the prestigious Plant Disease Journal. For that purpose,
they need to examine the seaweed and estimate the infection rate in
order to find out the spatial pattern in which the disease spreads.
Thus, each single plant plays an important role in shaping the big
picture about the spread of the disease. Interfering with the study
are the numerous manatees in the area. It turns out that seaweed
comprise an important part of manatees diet! The biologists want to
examine as much seaweed as possible before it is consumed by
manatees or is killed by pollution.
A total number of NN where 2≤N≤100,0002≤N≤100,000 manatees
are feeding in the area under study, and the team decides to move
each manatee to its favorite resting place in order complete their
measurements. Fortunately, the manatee will at the resting place
and not return (at least during the course of the study).
Unfortunately, the team is able to move only one manatee at a time.
Each manatee ii is TiTi hours (1≤Ti≤2,000,0001≤Ti≤2,000,000) away
from its favorite place. Furthermore, while waiting for transport,
a manatee consumes DiDi where 1≤Di≤1001≤Di≤100 pounds of seaweed
per hour. Moving manatee ii requires 2×Ti2×Ti hours (TiTi to get
there and TiTi to return). The team starts at the feeding area with
all the seagrass and transports the first manatee to its favorite
resting place, and then goes back to the feeding area, and so on.
We will assume that it takes no extra time in between traveling
back and forth.
Write a program to determine the best order in which the
team should move the manatees so that the total number of amount of
seaweed destroyed is minimized.
Input
* Line 1: A single integer N
* Lines 2 to N + 1: Each line contains two space-separated
integers, TiTi and DiDi, that describe the charecteristics of a
single manatee.
Output
The ouput is a single integer that is the minimum amount of
seaweed consumed while moving all the manatees from the study
area.
Sample Input
Sample Output
Here is the explanation. The team transports the manatees in
the following order: 6, 2, 3, 4, 1, 5. While they are transporting
the manatee number six in the list, the other manatees destroy 24
pounds of seaweed; next they will take second manatee, losing 28
pounds of of seaweed. For the manatees 3, 4, 1 they lose 16, 12,
and 6 pounds of seaweed respectively. When they pick manatee number
five, there are no more manatees eating in the study area, so the
loss during that move is zero. The total seaweed lost is 24 + 28 +
16 + 12 + 6 = 86.
No other order results in a small number. (How many possible
orders are there? N!N!)
Sample Input 2
Sample Output 2
Hints:
Create a record to represent manatees, create a list of
manatees and sort them. Finally, calculate the total seaweed
lost.
The ingenious part is how to compare two manatees. One
cannot just compare them by their "destructiveness" or by "time",
but rather by their ratio.
Here is a template program to help you get started
Template.java
Other helpful links: Greedy
method :

Template.java: