Sto provando a risolvere il problema butoaie e, fino ad ora, sono arrivato ad una soluzione in cui:
- Uso la ricerca binaria per trovare una possibile soluzione
- Calcolo per ogni stanza quanti insetticidi potenti ho bisogno
- Se in quella stanza il numero di insetticidi potenti di cui ho bisogno supera la quantità di giorni trovata con la ricerca binaria, esco automaticamente essendo una soluzione impossibile da risolvere
- Altrimenti, se la quantita di insetticidi potenti necessaria è maggiore di nPotenti * giorno, allora guardo a destra, altrimenti a sinistra.
Questo è il codice:
#include <bits/stdc++.h>
using namespace std;
int main() {
int N, K, P, Q;
cin >> N >> K >> P >> Q;
vector<int> stanze(N);
for (int i = 0; i < N; i++) {
cin >> stanze[i];
}
int nPotenti = N - K;
int nScarsi = K;
int potenti = Q;
int scarsi = P;
if (scarsi > potenti) {
swap(potenti, scarsi);
swap(nScarsi, nPotenti);
}
int left = 0;
int right = 1e7;
while (left <= right) {
int mid = (left + right) / 2;
int needed = 0;
for (int i = 0; i < N; i++) {
if (stanze[i] <= scarsi * mid) continue;
int duh = (stanze[i] - (scarsi * mid) + potenti - scarsi - 1) / (potenti - scarsi);
if (duh > mid) {
needed += nPotenti * mid + 1;
break;
}
needed += duh;
}
if (needed <= nPotenti * mid) {
right = mid - 1;
} else {
left = mid + 1;
}
}
cout << right + 1 << '\n';
}
. Credo che ci sia qualche problema con la mia ricerca binaria.