Lek_so_najniska_cena-[хеширање]

Во магацинот на една фармацевтска компанија се чуваат најразлични видови лекови.
За секој лек потребно е да се чуваат податоци за името на лекот, цената во денари и
намената на лекот. За поефикасен пристап до податоците за лековите, фармацевтската компанија
одлучила податоците да ги чува во хеш табела (CBHT) каде се сместуваат соодветните податоци.

Хеш табелата е достапна до крајните клиенти и истите може да пребаруваат низ внесените
податоци. Бидејќи на пазарот постојат повеќе лекови кои таргетираат иста болест, најчесто
клиентите го бараат оној лек кој има најниска цена. Па вашата задача е со користење на
хеш табелата, за дадена намена (болест), да го испечатите лекот кој има најниска цена на пазарот.
Доколку за бараната намена во магацинот нема лек се печати "Nema lek za baranata
namena vo magacin.".

Влез:

Најпрво е даден бројот на лекови - N, а потоа секој лек е даден во нов ред во форматот:

“Име на лек” “Намена” “Цена во денари”

На крај е дадена намената за која треба да се пронајде лекот со најниска цена.

Излез:

Името на лекот со најмала цена.


package com.example;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Hashtable;
import java.util.Map;

class MapEntry<K extends Comparable<K>,E> implements Comparable<K> {

    // Each MapEntry object is a pair consisting of a key (a Comparable
    // object) and a value (an arbitrary object).
    K key;
    E value;

    public MapEntry (K key, E val) {
        this.key = key;
        this.value = val;
    }

    public int compareTo (K that) {
        // Compare this map entry to that map entry.
        @SuppressWarnings("unchecked")
        MapEntry<K,E> other = (MapEntry<K,E>) that;
        return this.key.compareTo(other.key);
    }

    public String toString () {
        return "<" + key + "," + value + ">";
    }
}

class OBHT<K extends Comparable<K>,E> {

    // An object of class OBHT is an open-bucket hash table, containing entries
    // of class MapEntry.
    private MapEntry<K,E>[] buckets;

    // buckets[b] is null if bucket b has never been occupied.
    // buckets[b] is former if bucket b is formerly-occupied
    // by an entry that has since been deleted (and not yet replaced).

    static final int NONE = -1; // ... distinct from any bucket index.

    private static final MapEntry former = new MapEntry(null, null);
    // This guarantees that, for any genuine entry e,
    // e.key.equals(former.key) returns false.

    private int occupancy = 0;
    // ... number of occupied or formerly-occupied buckets in this OBHT.

    @SuppressWarnings("unchecked")
    public OBHT (int m) {
        // Construct an empty OBHT with m buckets.
        buckets = (MapEntry<K,E>[]) new MapEntry[m];
    }


    private int hash (K key) {
        // Translate key to an index of the array buckets.
        return Math.abs(key.hashCode()) % buckets.length;
    }


    public int search (K targetKey) {
        // Find which if any bucket of this OBHT is occupied by an entry whose key
        // is equal to targetKey. Return the index of that bucket.
        int b = hash(targetKey); int n_search=0;
        for (;;) {
            MapEntry<K,E> oldEntry = buckets[b];
            if (oldEntry == null)
                return NONE;
            else if (targetKey.equals(oldEntry.key))
                return b;
            else
            {
                b = (b + 1) % buckets.length;
                n_search++;
                if(n_search==buckets.length)
                    return NONE;

            }
        }
    }


    public void insert (K key, E val) {
        // Insert the entry <key, val> into this OBHT.
        MapEntry<K,E> newEntry = new MapEntry<K,E>(key, val);
        int b = hash(key); int n_search=0;
        for (;;) {
            MapEntry<K,E> oldEntry = buckets[b];
            if (oldEntry == null) {
                if (++occupancy == buckets.length) {
                    System.out.println("Hash tabelata e polna!!!");
                }
                buckets[b] = newEntry;
                return;
            }
            else if (oldEntry == former
                    || key.equals(oldEntry.key)) {
                buckets[b] = newEntry;
                return;
            }
            else
            {
                b = (b + 1) % buckets.length;
                n_search++;
                if(n_search==buckets.length)
                    return;

            }
        }
    }


    @SuppressWarnings("unchecked")
    public void delete (K key) {
        // Delete the entry (if any) whose key is equal to key from this OBHT.
        int b = hash(key); int n_search=0;
        for (;;) {
            MapEntry<K,E> oldEntry = buckets[b];

            if (oldEntry == null)
                return;
            else if (key.equals(oldEntry.key)) {
                buckets[b] = former;//(MapEntry<K,E>)former;
                return;
            }
            else{
                b = (b + 1) % buckets.length;
                n_search++;
                if(n_search==buckets.length)
                    return;

            }
        }
    }


    public String toString () {
        String temp = "";
        for (int i = 0; i < buckets.length; i++) {
            temp += i + ":";
            if (buckets[i] == null)
                temp += "\n";
            else if (buckets[i] == former)
                temp += "former\n";
            else
                temp += buckets[i] + "\n";
        }
        return temp;
    }


    public OBHT<K,E> clone () {
        OBHT<K,E> copy = new OBHT<K,E>(buckets.length);
        for (int i = 0; i < buckets.length; i++) {
            MapEntry<K,E> e = buckets[i];
            if (e != null && e != former)
                copy.buckets[i] = new MapEntry<K,E>(e.key, e.value);
            else
                copy.buckets[i] = e;
        }
        return copy;
    }
}

class Lek {
    String name;
    String purpose;
    int price;

    public Lek() {}
    public Lek(String name, String purpose, int price) {
        this.name = name;
        this.purpose = purpose;
        this.price = price;
    }

    public String getName() {
        return this.name;
    }
    public String getPurpose() {
        return this.purpose;
    }
    public int getPrice() {
        return this.price;
    }
    public void setName(String name) {
        this.name = name;
    }
    public void setPurpose(String purpose) {
        this.purpose = purpose;
    }
    public void setPrice(int price) {
        this.price = price;
    }
}

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        HashMap<Integer,Lek> lekovi = new HashMap<>(n);

        for (int i=0; i<n; i++) {
            String lek = br.readLine();
            String[] pomniza = lek.split(" ");
            String name = pomniza[0];
            String purpose = pomniza[1];
            int price = Integer.parseInt(pomniza[2]);
            Lek l = new Lek(name,purpose,price);
            lekovi.put(i,l);
        }

        String namena = br.readLine();
        String L = "";
        int min = 1000000;
        for (Map.Entry<Integer,Lek> curr : lekovi.entrySet()) {
            if (curr.getValue().purpose.equals(namena)) {
                if (curr.getValue().price < min) {
                    min = curr.getValue().price;
                    L = curr.getValue().name;
                }
            }
        }
        System.out.println(L);

    }
}



Пример:

Влез:

5
Analgin Glavobolka 80
Daleron Glavobolka 90
Lineks Bolki_vo_stomak 150
Spazmeks Bolki_vo_stomak 150
Loratadin Alergija 150

Glavobolka

Излез:

Analgin