Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.*;
- //TODO this exercise without using Vector
- public class Monsters {
- public static void main(String[] args){
- Scanner sc= new Scanner(System.in);
- int numberOfMonsters=sc.nextInt();
- int blasterStrength=sc.nextInt();
- int[] monsters=new int[numberOfMonsters];
- int k=0;
- while(k<numberOfMonsters){
- int input=sc.nextInt();
- monsters[k]=input;
- k++;
- }
- mergeSort(monsters,0,numberOfMonsters-1);
- //-1 is equal to dead monsters
- //Remove duplicates
- for(int i=0;i<numberOfMonsters-1;i++){
- if(monsters[i]==(monsters[i + 1]))
- monsters[i]=-1;
- }
- int lastMonsterIndex=numberOfMonsters-1;
- int numberOfBlasts=0;
- while(lastMonsterIndex > 0){
- //Remove last element with blast
- if(monsters[lastMonsterIndex] == -1){
- lastMonsterIndex--;
- continue;
- }
- monsters[lastMonsterIndex]=-1;
- lastMonsterIndex--;
- numberOfBlasts++;
- for(int j=0;j<numberOfMonsters;j++){
- //Blast all of them
- if(monsters[j] == -1)
- continue;
- monsters[j]=monsters[j] - blasterStrength;
- if(monsters[j] <= 0)
- monsters[j]=-1;
- }
- }
- System.out.println(numberOfBlasts);
- }
- private static void mergeSort(int[] arr,int begin, int end){
- if(begin>=end)
- return;
- int middle=(begin+end)/2;
- mergeSort(arr,begin,middle);
- mergeSort(arr,middle+1,end);
- merge(arr,begin,middle,end);
- }
- private static void merge(int[] arr,int begin,int middle,int end){
- int firstContainerSize=middle-begin+1;
- int[] firstContainer=new int[firstContainerSize];
- int secondContainerSize=end-middle;
- int[] secondContainer=new int[secondContainerSize];
- for(int i=0;i<firstContainerSize;i++)
- firstContainer[i]=arr[begin+i];
- for(int i=0;i<secondContainerSize;i++)
- secondContainer[i]=arr[middle+1+i];
- int i=0,j=0;
- int k=begin;
- while(i<firstContainerSize && j<secondContainerSize){
- if(firstContainer[i] < secondContainer[j]){
- arr[k]=firstContainer[i];
- i++;
- }
- else{
- arr[k]=secondContainer[j];
- j++;
- }
- k++;
- }
- while(i<firstContainerSize){
- arr[k]=firstContainer[i];
- k++;
- i++;
- }
- while(j<secondContainerSize){
- arr[k]=secondContainer[j];
- k++;
- j++;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement