Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.*;
- public class StepikAlgorithms {
- public static void main(String[] args){
- Scanner input = new Scanner(System.in);
- int thingsNumber = input.nextInt();
- int bagCapacity = input.nextInt();
- Bag bag = new Bag(bagCapacity);
- ArrayList<Thing> things = new ArrayList<>();
- for(int i = 0; i < thingsNumber; i++ ){
- int cost = input.nextInt();
- int weight = input.nextInt();
- things.add(new Thing(cost, weight));
- }
- Collections.sort(things, new Comparator<Thing>(){
- public int compare(Thing t1, Thing t2){
- return Float.compare(t2.specificCost, t1.specificCost);
- }
- });
- for(Thing thing:things){
- if(bag.freeCapacity > thing.weight){
- bag.freeCapacity -= thing.weight;
- bag.summaryCost += thing.cost;
- }else{
- bag.summaryCost += bag.freeCapacity * thing.specificCost;
- break;
- }
- }
- System.out.printf("%.3f",bag.summaryCost);
- }
- }
- class Thing{
- int cost;
- int weight;
- float specificCost;
- Thing(int cost, int weight){
- this.cost = cost;
- this.weight = weight;
- specificCost = (float) cost / weight;
- }
- }
- class Bag{
- int freeCapacity;
- double summaryCost;
- Bag(int capacity){
- this.freeCapacity = capacity;
- summaryCost = 0;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement