Problème : Maximisation des cleints et des profits dans la restauration

Énoncé du problème

Il existe n plats, le ième plat ayant un profit de \(a_i\) et une quantité de \(b_i\). Vous devez servir ces plats aux clients selon les règles suivantes :

1. Chaque client doit recevoir au moins un plat
2. Lors du service, les plats doivent être consécutifs en commençant par le premier plat. Par exemple, vous pouvez servir au client le premier, deuxième et troisième plat, mais pas uniquement le deuxième plat sans le premier, ou le premier et troisième plat sans le deuxième.

Déterminez le nombre maximum de clients que ces plats peuvent accueillir, et calculez le profit maximal correspondant.

Entrées et sorties

Il y a t cas de test. Pour chaque cas, la première ligne contient \(n\), indiquant le nombre de plats. Les deux lignes suivantes contiennent chacune n nombres : la première ligne contient \(a_1, a_2 ... a_n\), où le ième nombre représente le profit du ième plat, et la deuxième ligne contient \(b_1, b_2...b_n\), où le ième nombre représente la quantité du ième plat.

Plage des données

\(1\le n\le 10^{5}\),\(-10^{9}\le a_i\le10^{9}\)​,\(1\le b_i\le10^{5}\)

Entrée

2
3
2 -1 3
3 2 1
4
3 -2 3 -1
4 2 1 2

Sortie

Cas #1: 3 8
Cas #2: 4 13

Explication

Pour le premier cas de test, le nombre maximal de clients est 3. Une solution possible est : Le premier client reçoit le plat 1, avec un profit de 2. Le deuxième client reçoit le plat 1, avec un profit de 2. Le troisième client reçoit les plats 1, 2 et 3, avec un profit total de 2 + (-1) + 3 = 4.

Solutoin

1. Comme le premier plat doit toujours être servi, la quantité du premier plat détermine le nombre maximal de clients.

2. Pour calculer le profit maximal, nous utilisons une approche gloutonne. Lorsque les conditions sont satisfaites, nous privilégions d'abord les profits les plus élevés. Comme nous devons sélectionner des plats consécutifs de 1 à i à chaque fois, nous pouvons calculer d'abord la somme préfixe des profits des i premiers plats. Nous classons ensuite ces sommes par ordre décroissant. En parcourant de la plus grande à la plus petite, pour les n premiers plats avec une somme de sum, nous calculons la contribution en trouvant la quantité minimale restante min parmi les n premiers plats, puis ajoutons \(min*sum\) au résultat. Nous soustrayons ensuite min de la quantité de chaque plat parmi les n premiers. Cete opération peut être effectuée efficacement à l'aide d'un arbre segmentaire pour les requêtes et mises à jour par intervalle.

3. Étant donné que la valeur maximale peut atteindre \(10^{19}\), légèrement au-delà de la plage du type long long int, nous devons utiliser __int128 en C++. __int128 est un entier sur 128 bits, une extension de gcc, avec une plage de [\(-2^{127},2^{127}-1\)]. Cependant, gcc sous Windows ne prend pas en charge la compilation avec ce type, tandis que gcc sous Linux le supporte. Malheureusement, il n'existe pas de fonctions d'entrée/sortie standard, nous devons donc créer nos propres fonctions.

Fonctions d'entrée/sortie pour __int128

`inline __int128 lire(){// Lecture

  __int128 x=0,f=1;
  char ch=getchar();
  while(ch<'0'||ch>'9'){
​    if(ch=='-')
​      f=-1;
​    ch=getchar();
  }
  while(ch>='0'&&ch<='9'){
    x=x*10+ch-'0';
 ​   ch=getchar();
  }
  return x*f;
}
inline void afficher(__int128 x){// Affichage.
  if(x<0){
​    putchar('-');
​    x=-x;
  }
  if(x>9)
​    afficher(x/10);
  putchar(x%10+'0');
}

Code complet de la solution

#include<bits/stdc++.h>
#define scan(x) scanf("%d",&x)
#define scand(x,y) scanf("%d%d",&x,&y)
#define scanll(x) scanf("%lld",&x)
#define scanlld(x,y) scanf("%lld%lld",&x,&y)
#define imprimer(x) cout<<x<<endl
#define RAZ(a) memset(a,0,sizeof(a))
#define fg (rt<<1)
#define fd (rt<<1|1)
using namespace std;
typedef long long  ll;
typedef double db;
const double eps = 1e-7;
const double pi = acos(-1.0);
const int inf = 0x3f3f3f3f;
const ll linf = 0x3f3f3f3f3f3f3f3f;
const ll mod = ll(1e9)+7;
const int maxn=int(2e5)+500;
template<typename tp>inline tp bas(tp x){return x&(-x);}
template<typename tp1_>void debug(tp1_ x) {cout<<"*********** "<<x<<" *************"<<endl;}
template<typename tp1_,typename tp2_>void debug(tp1_ x,tp2_ y){cout<<"*********** "<<x<<" "<<y<<" *************"<<endl;}
struct P{int x;__int128 y;P(){}P(int _x,__int128 _y):x(_x),y(_y){}};
bool comparaison(const P elem1,const P elem2){
    if(elem1.y==elem2.y)return elem1.x>elem2.x;
    return elem1.y<elem2.y;
}
__int128 benefice[maxn];
__int128 quantite[maxn];
P somme[maxn];
int NumeroCas = 1;
struct noeud{
    __int128 total;
    __int128 retard;
}arbre[maxn<<2];
inline __int128 lire(){
    __int128 x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}

inline void afficher(__int128 x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)
        afficher(x/10);
    putchar(x%10+'0');
}

void construire(int rt,int l,int r){
    arbre[rt].total=arbre[rt].retard=0;
    if(l==r){
        arbre[rt].total = quantite[l];
        return ;
    }
    int mid = (l+r)>>1;
    construire(fg,l,mid);
    construire(fd,mid+1,r);
    arbre[rt].total = min(arbre[fg].total,arbre[fd].total);
}
void propager(int rt,int l,int r){
    if(arbre[rt].retard){
        __int128 val = arbre[rt].retard; 
        arbre[fg].total-=val;
        arbre[fd].total-=val;
        arbre[fg].retard += val;
        arbre[fd].retard += val;
        arbre[rt].retard = 0;
    }
}
void modifier(int rt,int l,int r,int L,int R,__int128 val){
    if(l>=L&&r<=R){
        arbre[rt].total -=val;
        arbre[rt].retard += val;
        return ;
    }
    propager(rt,l,r);
    int mid= (l+r)>>1;
    if(L<=mid)modifier(fg,l,mid,L,R,val);
    if(R>mid)modifier(fd,mid+1,r,L,R,val);
    arbre[rt].total = min(arbre[fg].total,arbre[fd].total);
}
__int128 interroger(int rt,int l,int r,int L,int R){
    if(l>=L&&r<=R){
        return arbre[rt].total;
    }
    propager(rt,l,r);
    int mid = (l+r)>>1;
    __int128 res = inf;
    if(L<=mid)res=min(res,interroger(fg,l,mid,L,R));
    if(R>mid)res=min(res,interroger(fd,mid+1,r,L,R));
    return res;
}
void resoudre() {
    int n;
    scan(n);
    somme[0].y = 0;
    for(int i=1;i<=n;i++){
        benefice[i]=lire();
        somme[i].x=i;
        somme[i].y=benefice[i]+somme[i-1].y; 
    }
    for(int i=1;i<=n;i++)quantite[i]=lire();
    sort(somme+1,somme+n+1,comparaison);
    __int128 clients = quantite[1];
    construire(1,1,n);
    __int128 resultat = 0;
    for(int i=n;i>=1;i--){
        __int128 cnt = interroger(1,1,n,1,somme[i].x);
        resultat+= cnt*somme[i].y;
        modifier(1,1,n,1,somme[i].x,cnt);
    }
    printf("Cas #%d: ",NumeroCas);
    afficher(clients);
    printf(" ");
    afficher(resultat);
    printf("\n");

}
void Principal(){
    int _;
    scan(_);
    while(_--)
    resoudre(),++NumeroCas;
    
}
//#define _Debug
int main(){
    #ifdef _Debug
    freopen("donnees.in","r",stdin);
    clock_t debut = clock();
    Principal();
    clock_t fin = clock();
    cout<<"temps écoulé : "<<(fin-debut)<<endl; 
    #else
    Principal();
    #endif
    return 0;
}