Удалить элементы для заданного количества итераций

Вот предлагаемый подход.

1. Построить карту от value до count_of_value
2. Узнайте, сколько значений имеют числа, НЕ кратные k. Это count_incommensurate то, от скольких значений вы не можете избавиться.
3. Для остальных значений создайте массив по возрастанию count_of_value / k.
4. Теперь создайте поиск по количеству итераций, сколько существует удаляемых значений.
5. Выполните поиск.

В вашем случае эти шаги приводят к следующему. Исходная карта:

{
    0: 1,
    1: 2,
    2: 1,
    5: 1,
}

Все значения делятся на k=1, поэтому count_incommensurate = 0.

Массив отсчетов в порядке возрастания равен [1, 1, 1, 2].

Теперь мы подошли к массиву поиска. Он начинается с 0 с общего количества отсчетов, которое равно 4. Итак [4, .... Теперь мы записываем каждое число количество раз, прежде чем уменьшить, и останавливаемся на 0. Таким образом, мы получаем [4, 3, 2, 1, 1]. Другими словами

counts: [1, 1, 1, 2   ]
lookup: [4, 3, 2, 1, 1]

Если бы наши подсчеты были [1, 2, 3], мы бы вместо этого получили

counts: [1, 2   , 3      ]
lookup: [3, 2, 2, 1, 1, 1]

Но вернемся к тому, что мы на самом деле получили. [4, 3, 2, 1, 1] — это массив, начинающийся с 0, для нашего поиска, а все, что находится за его пределами, — это 0.

Теперь делаем наши поиски.

Поиск 1 плюс несоизмеримое дает нам 3 + 0 = 3.

Поиск 5 не в конце, поэтому мы получаем 0 + 0 = 0.

Поиск 3 дает нам 1 + 0 = 1.

Если мы повторим это упражнение с k=2, мы обнаружим, что count_incommensurate — это 3, а наш поисковый массив окажется [1]. (После нулевых итераций элемент 1 все еще существует.) Поскольку все поиски не в конце, мы получим 3, 3, 3 в качестве нашего ответа.

Время для этого алгоритма O(N + Q). Учитывая, что для сканирования значений требуется O(N), а для сканирования запросов — O(Q), вы не можете улучшить это более чем на постоянный коэффициент. Небольшой момент, который следует упомянуть, заключается в том, что исходный массив счетчиков (в данном случае [1, 2, 1, 1]) необходимо отсортировать, что добавляет временную сложность O(N log N) к задаче.

Это ответ, который я закодировал на основе алгоритма, предложенного @btilly.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;


class Main {
    public static void main(String args[] ) throws Exception {
           
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String[] num_arr;
        num_arr = br.readLine().split("\\s");
        
        int [] nkq_arr = new int[3];
        for(int i=0;i<3;i++)
        {   
            nkq_arr[i] = Integer.parseInt(num_arr[i]);
        }

        int N = nkq_arr[0];
        int K = nkq_arr[1];
        int Q = nkq_arr[2];
        
        int i = 0,j = 0;

        String[] param_arr;
        param_arr = br.readLine().split("\\s");
        
        int [] arr = new int[N];
        while(i < N)
        {
            arr[i] = Integer.parseInt(param_arr[i]);
            i++;
        }

        int[] queries = new int[Q];
        while(j < Q)
        {
            queries[j] = Integer.parseInt(br.readLine());
            j++;
        }

        for(int c=0;c<Q;c++)
        {
          System.out.println(minFeatures(arr,N,K,queries[c]));
        } 

    }
    static int minFeatures (int [] arr, int N, int K, int query)
    {
      HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
      int count=0;
      for(int i=0;i<N;i++)
      {
        if (!map.containsKey(arr[i]))
        {
          map.put(arr[i],1);
          count++;
        }
        else
        {
          Integer b = map.get(arr[i]);
          b+=1;
          map.replace((Integer)arr[i],b);
        }
      }
      
      List<Integer> relevant_arr = new ArrayList();
      int improper_count=0;
      int relevant_arr_length = 0;

      for(Integer val : map.values())
      {
        if (val%K==0)
        {
          relevant_arr.add(val/K);
          relevant_arr_length++;
        }
        else
        {
          improper_count++;
        }
      }
      Collections.sort(relevant_arr);
      List<Integer> lookUp_arr = new ArrayList();

      int alpha = 0;
      int overall_length=0;

      while(alpha < relevant_arr_length)
      {
        int number_of_times = relevant_arr.get(alpha);
        int beta = number_of_times;

        while(beta > 0)
        {
          lookUp_arr.add(count);
          beta--;
          overall_length++;
        }
        count--;
        alpha++;
      }

      
      if (query > overall_length-1)
      {
        return improper_count;
      }      
      else
      {
        return improper_count + lookUp_arr.get(query);
      }
  }
}

Python Реализация алгоритма, предложенного @btilly.

from collections import defaultdict

def evaluateMin(arrQ,k,queryArr):
  ans = []
  countMap = defaultdict(lambda : 0)
  for value in arrQ:
    countMap[value] +=1
  
  counts=[]
  presentEveryTime = 0
  for value in countMap:
    if countMap[value] % k != 0:
      presentEveryTime +=1
    else:
      counts.append(int(countMap[value]/k))

  # Creating Lookup Array
  counts = sorted(counts)
  lookup = []
  # print(counts)
  appender = len(counts)
  for count in counts:
    for i in range(count):
      lookup.append(appender)
    
    if appender != 1:
      appender -=1
  # print(lookup,presentEveryTime)
  for query in queryArr:
    if query >= len(lookup):
      ans.append(0+presentEveryTime)
    else: 
      ans.append(lookup[query]+presentEveryTime)

  return ans

print(evaluateMin([5,0,1,2,1,1,1],2,[1,5,3,0,2]))