Les secrets de la célèbre prison Habs Qara située à Meknès - Programmation compétitive

Ces dernières années, les chercheurs ont trouvé des livres manuscrits intéressants numérotés sur l'histoire du sultan du Maroc de 1672 à 1727, Moulay Ismail Ibn Sharif. Les chercheurs pensent que ces livres révéleront les secrets de la célèbre prison Habs Qara. Alors, ils ont décidé de lire attentivement ces livres.

Pour accélérer la lecture, les chercheurs ont décidé de séparer la tâche entre eux de manière égale, de sorte que chaque chercheur est chargé de lire des livres consécutifs de telle sorte que le nombre maximum de pages soit minimisé.

Lorsqu'un chercheur commence la lecture d'un livre, il doit terminer la lecture, donc chaque livre ne peut être lu que par un seul chercheur.

Entrée

La première ligne contient le nombre de livres (n) et le nombre de chercheurs (m). La ligne suivante contient le nombre de pages dans chaque livre.

Sortie

Le nombre maximum de pages pouvant être affectées à chaque chercheur.

Exemples

Entrée du programme	Sortie du programme
2 2 15 40	40
4 5 12 10 16 30	-1
5 3 10 20 30 25 40	55

Solution

L'idée est d'utiliser la recherche binaire. Nous fixons une valeur pour le nombre de pages c'est le milieu entre le minimum et le maximum actuels. Nous initialisons respectivement le minimum et le maximum à 0 et à la somme de toutes les pages. Si un milieu actuel peut être une solution, alors nous cherchons dans la moitié inférieure, sinon nous cherchons dans la moitié supérieure.

Maintenant la question se pose, comment vérifier si une valeur milieu est faisable ou non ? En fait, nous devons vérifier si nous pouvons attribuer des pages à tous les chercheurs de manière à ce que le nombre maximum ne dépasse pas la valeur actuelle. Pour ce faire, nous assignons séquentiellement des pages à chaque chercheur tant que le nombre actuel de pages assignées ne dépasse pas la valeur. Dans ce processus, si le nombre de chercheurs devient supérieur à m, alors la solution n'est pas faisable. Sinon, c'est faisable.

Python
C++

import sys

def faisable(pages,n, m, min_actuel):
    besoinenchercheurs = 1
    somme_actuelle = 0

    for i in range(n):
        # vérifier si le nombre actuel de pages est supérieur à min_actuel, 
        # ce qui signifie que nous obtiendrons le résultat après le nombre milieu de pages.
        if (pages[i] > min_actuel): return False

        if (somme_actuelle + pages[i] > min_actuel):
            besoinenchercheurs+=1
            somme_actuelle = pages[i]

            # si le nombre de chercheurs requis est supérieur au nombre de chercheurs donné, retournez false.
            if (besoinenchercheurs > m):    return False
        else:
            somme_actuelle += pages[i]
    
    return True

def solution(pages, n, m):
    # Retourner -1 si le nombre de livres est inférieur au nombre de chercheurs.
    if (n < m):
        return -1
    
    # calculer la somme des pages
    somme=sum(pages)

    debut = 0; fin = somme
    maxpages = sys.maxsize
 
    while (debut <= fin):
        milieu = (debut + fin) // 2
        if (faisable(pages, n, m, milieu)):
            maxpages = milieu
            fin = milieu - 1
        else:
            debut = milieu + 1

    return maxpages

        

n,m = map(int, sys.stdin.readline().strip().split())
pages=list(map(int, sys.stdin.readline().strip().split()))

pages.sort()
print(solution(pages, n, m))

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

using namespace std;

bool faisable(const vector<int> &pages, int n, int m, int min_actuel)
{
    int besoinenchercheurs = 1;
    int somme_actuelle = 0;
 
    for (int i = 0; i < n; i++)
    {
        /* 
            vérifier si le nombre actuel de pages est supérieur à min_actuel, 
            ce qui signifie que nous obtiendrons le résultat après le nombre milieu de pages.
        */
        if (pages[i] > min_actuel)
            return false;

        /*
            compter combien de chercheurs sont nécessaires pour distribuer min_actuel pages. 
        */
        if (somme_actuelle + pages[i] > min_actuel)
        {
            besoinenchercheurs++;
            somme_actuelle = pages[i];

            // si le nombre de chercheurs requis est supérieur au nombre de chercheurs donné, retournez false.
            if (besoinenchercheurs > m)
                return false;
        }
        else
            somme_actuelle += pages[i];
    }
    return true;
}

int solution(vector<int> pages, int n, int m)
{
    // Retourner -1 si le nombre de livres est inférieur au nombre de chercheurs.
    if (n < m)
        return -1;
    
    // calculer la somme des pages
    long long somme=accumulate(pages.begin(), pages.end(), 0);

    int debut = 0, fin = somme;
    int maxpages = INT_MAX;
 
    while (debut <= fin)
    {
        int milieu = (debut + fin) / 2;
        if (faisable(pages, n, m, milieu))
        {
            maxpages = milieu;
            fin = milieu - 1;
        }
        else
            debut = milieu + 1;
    }
    return maxpages;
}

int main()
{
    int n, m, val;
    cin >> n >> m;
    vector<int> pages;
    for(int i=0;i<n;i++){
        cin>> val;
        pages.push_back(val);
    }

    sort(pages.begin(),pages.end());

    cout << solution(pages,n,m);
    
    return 0;
}

Les secrets de la célèbre prison Habs Qara située à Meknès - Programmation compétitive

Problèmes résolus dans la programmation compétitive - Guide complet

Sommaire