[Problème des Vaches Anragées]

Lien vers le problème: Vaches Enragées Approche: Un problème classique de recherche binaire de réponse, similaire au problème des pierres sautantes. On binaire la distance minimale entre chaque étable, puis on vérifie si la réponse est valide en l'énumérant.

Code:

Cliquer pour voir le code``` #include #include #include using namespace std; typedef long long ll; const int MAX = 1e5 + 5; int nbEtables, nbVaches, gauche, droite, reponse, milieu; int positions[MAX], prefix[MAX];

inline ll lireEntier() { ll x = 0; negatif = 0; char caracteer = getchar(); while (caractere < '0' || caractere > '9') { negatif |= (caractere == '-'); caractere = getchar(); } while (caractere >= '0' && caractere <= '9') { x = (x << 3) + (x << 1) + (caractere ^ 48); caractere = getchar(); } return negatif ? ~x + 1 : x; }

bool verifier(int distance) { int positionSuivante = positions[1] + distance, compte = 1; for(int i = 2; i <= nbEtables; ++i) { if(positions[i] >= positionSuivante) { ++compte; positionSuivante = positions[i] + distance; } } return compte >= nbVaches; }

int main() { nbEtables = lireEntier(), nbVaches = lireEntier(); for (int i = 1; i <= nbEtables; ++i) { positions[i] = lireEntier(); } sort (positions + 1, positions + nbEtables + 1); droite = positions[nbEtables] - positions[1]; while(gauche <= droite) { milieu = (gauche + droite) >> 1; if(verifier(milieu)) { reponse = milieu; gauche = milieu + 1; } else { droite = milieu - 1; } } printf("%d\n", reponse); return 0; }

[Meilleures Clôtures pour Vaches]
-------------------

Lien vers le problème: Meilleures Clôtures pour Vaches
Approche: Encore une recherche binaire de réponse, mais impliquant des nombres à virgule flottante, ce qui nécessite une gestion de la précision. On binaire la moyenne, on énumère, on enregistre la différence entre chaque nombre et la moyenne, puis on calcule la somme. Si cette somme est supérieure ou égale à 0, la réponse est valide. Il suffit qu'une intervalle soit valide pour que la réponse soit correcte, car le problème demande simplement l'existence d'une solution. Le reste concerne la gestion de la précision.

Code:

Cliquer pour voir le code```
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
const int MAX = 1e5 + 5;
const double PRECISION = 1e-7;
ll nbElements, longueur;
double gauche, droite;
double valeurs[MAX], sommes[MAX];

inline ll lireEntier() {
	ll x = 0;
    negatif = 0;
	char caractere = getchar();
	while (caractere < '0' || caractere > '9') {
		negatif |= (caractere == '-');
		caractere = getchar();
	}
	while (caractere >= '0' && caractere <= '9') {
		x = (x << 3) + (x << 1) + (caractere ^ 48);
		caractere = getchar();
	}
	return negatif ? ~x + 1 : x;
}

bool verifier(double moyenne) {
	sommes[0] = 0;
	for(int i = 1; i <= nbElements; ++i) {
		sommes[i] = sommes[i - 1] + valeurs[i] - moyenne;
	}
	double minimum = 0x3f3f3f3f;
	for(int i = longueur; i <= nbElements; ++i) {
		minimum = min(minimum, sommes[i - longueur]);
		if(sommes[i] >= minimum)	return true;
	}
	return false;
}

int main() {
	nbElements = lireEntier(), longueur = lireEntier();
	for (int i = 1; i <= nbElements; ++i) {
		scanf("%lf", &valeurs[i]);
	}
	double gauche = -1, droite = 2e3 + 1;
	while(droite - gauche > PRECISION) {
		double milieu = (gauche + droite) / 2;
		if(verifier(milieu)) {
			gauche = milieu;
		}
		else {
			droite = milieu;
		}
	}
	printf("%d",int(droite * 1000));
	return 0;
}

[Segmentation de Suite II]

Lien vers le problème: Segmentation de Suite II Approche: En fait, comparé à la Segmentation de Suite I, cela ajoute simplement une recherche binaire de réponse. Le processus de vérification reste identique. Voici le code :

Code:

Cliquer pour voir le code``` #include #include using namespcae std; typedef long long ll; const int MAX = 1e5 + 5; ll nbElements, nbSegments; ll gauche, droite, reponse, total; ll elements[MAX];

inline ll lireEntier() { ll x = 0; negatif = 0; char caractere = getchar(); while(caractere < '0' || caractere > '9') { negatif |= (caractere == '-'); caractere = getchar(); } while(caractere >= '0' && caractere <= '9') { x = (x << 3) + (x << 1) + (caractere ^ 48); caractere = getchar(); } return negatif ? ~x + 1 : x; }

bool verifier(ll seuil) { ll somme = 0, compte = 1; for (int i = 1; i <= nbElements; ++i) { if(elements[i] > seuil) return false; if(somme + elements[i] > seuil) { somme = 0; ++compte; } somme += elements[i]; } return compte <= nbSegments; }

int main() { nbElements = lireEntier(), nbSegments = lireEntier(); gauche = 1e12; for (int i = 1; i <= nbElements; ++i) { elements[i] = lireEntier(); total += elements[i]; gauche = min(gauche, elements[i]); } droite = total; while(gauche < droite) { ll milieu = (gauche + droite) >> 1; if(verifier(milieu)) { reponse = milieu; droite = milieu; } else { gauche = milieu + 1; } } printf("%lld\n", reponse); return 0; }

[Propagation]
------

Lien vers le problème: Propagation
Approche: Il y a une règle ici : si un point est atteint par la propagation avant la minute i, alors la somme de ses coordonnées x et y ne dépasse pas i. Ainsi, si la distance entre deux points ne dépasse pas 2 × i, ces deux points peuvent former une composante connexe en i minutes. On effectue alors une recherche binaire sur le temps, en vérifiant selon la méthode décrite précédemment.

Code:

Cliquer pour voir le code```
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
const int MAX = 60;
int nbPoints, gauche, droite, reponse;
int coordX[MAX], coordY[MAX], parent[MAX];

inline ll lireEntier() {
	ll x = 0;
    negatif = 0;
	char caractere = getchar();
	while (caractere < '0' || caractere > '9') {
		negatif |= (caractere == '-');
		caractere = getchar();
	}
	while (caractere >= '0' && caractere <= '9') {
		x = (x << 3) + (x << 1) + (caractere ^ 48);
		caractere = getchar();
	}
	return negatif ? ~x + 1 : x;
}

int trouver(int point) {
	return parent[point] == point ? parent[point] : parent[point] = trouver(parent[point]);
}

bool verifier(int temps) {
	for(int i = 1; i <= nbPoints; ++i) {
		parent[i] = i;
	}
	for(int i = 1; i < nbPoints; ++i) {
		for(int j = i + 1; j <= nbPoints; ++j) {
			int distance = abs(coordX[i] - coordX[j]) + abs(coordY[i] - coordY[j]);
			if(distance <= (temps << 1)) {
				int racineX = trouver(i), racineY = trouver(j);
				parent[racineX] = racineY;
			}
		}
	}
	int compte = 0;
	for(int i = 1; i <= nbPoints; ++i) {
		if(parent[i] == i)	++compte;
	}
	return compte == 1;
}

int main() {
	nbPoints = lireEntier();
	for(int i = 1; i <= nbPoints; ++i) {
		coordX[i] = lireEntier(), coordY[i] = lireEntier();
	}
	gauche = 1, droite = 1e9;
	while(gauche < droite) {
		int milieu = (gauche + droite) >> 1;
		if(verifier(milieu)) {
			reponse = milieu;
			droite = milieu;
		}
		else {
			gauche = milieu + 1;
		}
	}
	printf("%d\n", reponse);
	return 0;
}

Fin

Je viens de réaliser que tous les problèmes de recherche binaire sont en fait des recherches binaires de réponse. Les problèmes de recherche ternaire seront ajoutés plus tard lorsque je les aurai étudiés. Préparation pour aborder la partie sur la recherche !