Задатак: Највреднији поклон

У продавници се налази \(n\) поклона, поређаних по цени у растућем редоследу. Сваки купац жели да купи што вреднији поклон, али тако да не прекорачи свој буџет.

За сваког купца потребно је одредити цену најскупљег поклона који може да приушти.

Опис улаза

• У првом реду налази се цео број \(n\) \((1 \le n \le 10^5)\) — број поклона.
• У другом реду налази се \(n\) целих бројева \(c_1, c_2, \dots, c_n\) \((1 \le c_i \le 10^9)\), који представљају цене поклона.
• У трећем реду налази се цео број \(q\) \((1 \le q \le 10^5)\) — број купаца.
• У четвртом реду налази се \(q\) целих бројева \(b_1, b_2, \dots, b_q\) \((1 \le b_i \le 10^9)\), где \(b_i\) представља буџет \(i\)-тог купца.

Опис излаза

За сваког купца исписати по један цео број у засебном реду – цену најскупљег поклона који је мањи или једнак од \(x_i\).

Уколико такав поклон не постоји, исписати \(-1\).

Пример

Улаз

5
20 10 70 35 50
3
5 40 70

Излаз

-1
35
70

Решење

Након што се низ цена сортира, задатак се веома ефикасно може решити бинарном претрагом, примењену изнова на сваки буџет \(b_i\). Кренимо од следеће инваријанте. Током петље одржаваћемо два показивача l и d, тако да су све цене лево од показивача l такве да се поклон може купити за дати буџет, а све цене десно од показивача d такве да се поклон не може купити за дати буџет, док су на позицијама из интервала \([l, d]\) цене које алгоритам још није испитао. Дакле, претпоставимо да је стање низа следеће:

У почетку су све цене непрегледане, па интервал \([l, d]\) треба да се поклопи са целим низом, тј. \(l\) треба иницијализовати на \(0\), а \(d\) на \(n-1\).

У сваком кораку петље одређујемо средишњу позицију \(s\) у интервалу \([l, d]\). Да би се смањила могућност прекорачења, ту позицију уместо помоћу \(\left\lfloor{\frac{l+d}{2}}\right\rfloor\), можемо израчунати помоћу \(l + \left\lfloor{\frac{d-l}{2}}\right\rfloor\).

• Ако се елемент на позицији \(s\) уклапа у дати буџет тј. ако је цена \(c_s \leq b_i\), тада се, због сортираности, могу приуштити и сви поклони на позицијама лево од \(s\), па инваријанта остаје на снази ако се \(l\) помери на позицију \(s+1\).

• У супротном, ако је \(b_i < c_s\), тада се, због сортираности, не може пришутити ни један поклон на позицијама десно од \(s\), па инваријанта остаје на снази ако се \(l\) помери на позицију \(s-1\).

Петља се извршава док год има непрегледаних цена, тј. док је интервал \([l, d]\) непразан. Када се претрага заврши, стање у низу је следеће.

На основу инваријанте знамо да се сваки елемент лево од \(l\) може приуштити, а да се ни један десно од \(d\) не може, па се стога тражени највреднији поклон налази на позицији \(d=l-1\). Ако су сви поклони прескупи, крајње вредности ће бити \(d=-1\) и \(l=0\), па се враћањем вредности \(d\) и у том случају добија коректан резултат.

Функција се зауставља јер се у сваком кораку ширина интервала \([l, d]\) стриктно смањује (захваљујући заокруживању наниже приликом одређивања средишње позиције \(s\)).

// vraca poziciju u sortiranom nizu cene najvrednijeg poklona
// koji se moze kupiti za dati budzet ili
// -1 ako su svi pokloni preskupi
int najvredniji_poklon(const vector<int>& cene, int budzet) {
  int n = cene.size();
  int l = 0, d = n - 1;
  while (l <= d) {
    int s = l + (d - l) / 2;
    if (cene[s] <= budzet)
      l = s + 1;
    else
      d = s - 1;
  }
  return d;
}

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// vraca poziciju u sortiranom nizu cene najvrednijeg poklona
// koji se moze kupiti za dati budzet ili
// -1 ako su svi pokloni preskupi
int najvredniji_poklon(const vector<int>& cene, int budzet) {
  int n = cene.size();
  int l = 0, d = n - 1;
  while (l <= d) {
    int s = l + (d - l) / 2;
    if (cene[s] <= budzet)
      l = s + 1;
    else
      d = s - 1;
  }
  return d;
}

int main() {
  int n;
  cin >> n;
  vector<int> cene(n);
  for (int i = 0; i < n; i++)
    cin >> cene[i];
  sort(begin(cene), end(cene));
  int q;
  cin >> q;
  for (int i = 0; i < q; i++) {
    int budzet;
    cin >> budzet;
    int k = najvredniji_poklon(cene, budzet);
    if (k == -1)
      cout << -1 << endl;
    else
      cout << cene[k] << endl;
  }
  return 0;
}