Alqoritm Analizi

Əgər müəyyən bir kanistrin həcmi $k$-dan çoxdursa, bütün suyu evə daşımaq mümkün deyil, biz “Mümkün deyil” çıxış edirik.

Kanistrləri artan həcmə görə sıralayırıq. Ən böyük kanistri ən kiçik ilə birlikdə daşımağa çalışacağıq. Əgər bu mümkün deyilsə, onda ən böyük kanistri evə tək başına daşımak lazımdır. Əgər mümkündürsə – onda ən böyük və ən kiçik kanistr nəzərdən çıxarılır, sonra qalan kanistrlər üçün problemi oxşar şəkildə həll edirik.

Nümunə

Məsələ ifadəsindən olan nümunəni nəzərdən keçirək. Mövcud olan kanistrlərin həcmləri: 1, 2, 3, 3-dir. Sergey bir dəfədə ən çox $k=4$ litr su daşıya bilər. Ən kiçik və ən böyük kanistrin həcmlərinin cəmi 1 + 3 = 4, bu da $k$-dan çox deyil. Buna görə, ilk dəfə Sergey bu iki kanistri daşıyacaq.

Qalan kanistrlər 2 və 3-dür. Ən kiçik və ən böyük kanistrin həcmlərinin cəmi 2 + 3 = 5, bu da $k$-dan çoxdur. Buna görə, ikinci dəfə ən böyük kanistri tək başına evə daşımak lazımdır.

Üçüncü dəfə Sergey son kanistri 2 litr həcmində evə aparacaq.

Alqoritm Tətbiqi

Kanistrlərin həcmlərini bir massivdə m saxlayırıq.

vector<int> m;

// Giriş məlumatlarını oxuyuruq.
m.resize(n);
for (i = 0; i < n; i++)
    scanf("%d", &m[i]);

// Kanistrlərin həcmlərini sıralayırıq.
sort(m.begin(), m.end());

// Suyun daşınma sayını `res` dəyişənində hesablayırıq.
res = 0;

// İki göstərici təyin edirik: `a` massivin başlanğıcında, `b` – sonunda.
a = 0; b = m.size() - 1;

// Əgər ən böyük kanistr `k`-dan çoxdursa, bütün suyu daşımaq mümkün deyil.
if (m[b] > k) {
    printf("Impossible\n"); 
    return 0;
}

// Suyu daşımaq.
while (a <= b) {
    // Əgər ən kiçik və ən böyük kanistrin cəmi `k`-dan çoxdursa, bir dəfədə yalnız ən böyük kanistr daşına bilər.
    if (m[a] + m[b] > k) b--;
    // Əks halda, iki kanistr daşınır: ən kiçik və ən böyük.
    else { a++; b--; }
    res++;
}

// Cavabı çıxış edirik.
printf("%d\n", res);