Qazanlar və qapaqlar#7335

Qazanlar və qapaqlar (Həll təhlili)

Qapaqların radiuslarını və qazanların radiuslarını artan sıra ilə sıralayaq. Ən kiçik qazan üçün onu örtə biləcək ən kiçik qapağı tapaq. Sonra ikinci ən kiçik qazan üçün ona uyğun ən kiçik qapağı tapaq və s. Cavab qapaqlarla örtülə bilən qazanların sayı olacaqdır.

Nümunə

Verilmiş nümunə üçün ən çox neçə qazana qapaq seçilə biləcəyinə baxaq.

Alqoritmin realizasiyası

Qazanların və qapaqların radiuslarını saxlayacağımız massivləri elan edək.

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

Giriş məlumatlarını oxuyuruq.

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]);

Qazanların və qapaqların radiuslarını sıralayırıq.

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

Acgöz metoddan istifadə edərək, hər dəfə ən kiçik qazanı örtə biləcək ən kiçik qapağı axtarırıq.

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

Örtülmüş qazanların sayını çap edirik.

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

Java realizasiyası

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 realizasiyası

Giriş məlumatlarını oxuyuruq.

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

Qazanların və qapaqların radiuslarını sıralayırıq.

pan.sort()
lid.sort()

Acgöz metoddan istifadə edərək, hər dəfə ən kiçik qazanı örtə biləcək ən kiçik qapağı axtarırıq.

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

Örtülmüş qazanların sayını çap edirik.

print(i)