Каструлі та кришки#7335

Каструлі та кришки (Розбір)

Відсортуємо за зростанням радіуси кришок і радіуси каструль. Для найменшої каструлі знайдемо найменшу кришку, якою її можна накрити. Далі для другої найменшої каструлі знайдемо найменшу кришку, що їй підходить, і так далі. Відповіддю буде кількість каструль, яку можна накрити кришками.

Приклад

Розглянемо, якій найбільшій кількості каструль можна підібрати кришки для заданого прикладу.

Реалізація алгоритму

Оголосимо масиви, в яких будемо зберігати радіуси каструль і кришок.

#define MAX 1010
int pan[MAX], lid[MAX];

Читаємо вхідні дані.

scanf("%d %d",\&n,\&m);
for(i = 0; i < n; i++)
  scanf("%d",\&pan[i]);
for(i = 0; i < m; i++)
  scanf("%d",\&lid[i]);

Сортуємо радіуси каструль і кришок.

sort(pan,pan+n);
sort(lid,lid+m);

Використовуючи жадібний метод, шукаємо щоразу найменшу кришку, якою можна накрити найменшу каструлю.

for (i = j = 0; (i < n) \&\& (j < m); j++)
  if (pan[i] <= lid[j]) i++;

Виводимо кількість накритих каструль.

printf("%d\n",i);

Java реалізація

import java.util.*;
 
public class Main
{
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    int n = con.nextInt();
    int m = con.nextInt();
    Integer pan[] = new Integer[n];
    for(int i = 0; i < n; i++)
      pan[i] = con.nextInt();
   
    Integer lid[] = new Integer[n];
    for(int i = 0; i < m; i++)
      lid[i] = con.nextInt();
   
    Arrays.sort(pan);
    Arrays.sort(lid);

    int i = 0;
    for(int j = 0; (i < n) \&\& (j < m); j++)
        if (pan[i] <= lid[j]) i++;
    
    System.out.println(i);
    con.close();
  }
}

Java

Python реалізація

Читаємо вхідні дані.

n, m = map(int,input().split())
pan = list(map(int,input().split()))
lid = list(map(int,input().split()))

Сортуємо радіуси каструль і кришок.

pan.sort()
lid.sort()

Використовуючи жадібний метод, шукаємо щоразу найменшу кришку, якою можна накрити найменшу каструлю.

i = j = 0
while i < n and j < m:
  if pan[i] <= lid[j]: i += 1
  j += 1

Виводимо кількість накритих каструль.

print(i)