Uva 1062 — Containers

PROBLEM Link Uva1062 Submit Link

Explanation

This problem can be solved through the use of a vector of stacks. The premise is that a stack of containers must be separated into S stacks such that the top crate on at least one of the stacks can be loaded on the current ship. The ships load in alphabetical order, so we can stack with respect to the alphabet.

Start with one stack and add the first letter. From then on, check each stack to see if the current letter can be added we must add container to the stack whose top is greater than current and in all those stacks we must choose nearest.
(Although for this solution greedy solution(choose any whose top is greater than current) but it is better to choose best of them all as greedy solution might fail in some cases)

If the current letter is less than or equal to the one on top of a stack, add it to that stack. Otherwise, check the next one. If none of the letters on top of any stacks can support the current container, add a new stack to the vector and increment your count.

Input

A 
CBACBACBACBACBA 
CCCCBBBBAAAA 
ACMICPC
ABCDEFGHIJKLMNOPQRSTUVWXYZ
AAQGHIAEIBJAEFNHBAJKLWENHRGKLAJLKAWLREJIGNQRNHLEGJKLQBNWEVKLBMAEKLBN
ANKLAGRABZBQHERLUIGQYNOVIUEYQBNIWUECTMQOIWEUMZHJGCIWEYRNQIUWEY
end

Output

Case 1: 1
Case 2: 3
Case 3: 1
Case 4: 4
Case 5: 26
Case 6: 12
Case 7: 11

CODE in C++

#include<bits/stdc++.h>
using namespace std;
int  solve(string & s){
    vector<stack<char> >vs;
for(int i=0;i<s.size();i++){
        if(vs.empty()){
            stack<char>st;
            vs.push_back(st);
            vs[0].push(s[i]);
            continue;
        }
bool flag=false;
   /* 
     flag will be used to check whether we found any container whose top 
     is greater than the current container
    */   
        int mini=-1;
      // mini will be used to store the index of nearest appropriate container stack
        for(int j=0;j<vs.size();j++){
            if(s[i]<=vs[j].top()){
                flag=true;
                if(mini==-1)
                    mini=j;
                else if(vs[mini].top()>vs[j].top()){
                    mini=j;
                }
            }
        }
if(!flag)
        {
            stack<char>st;
            vs.push_back(st);
            vs[vs.size()-1].push(s[i]);
        }
else{  //if we could not able to place the container on any of previous container
            vs[mini].push(s[i]);
        }
    }
return vs.size();//returning size of vector of stacks
}
int main()
{
    string s;
    cin>>s;
    int i=1;
    while(s!="end"){
        cout<<"Case "<<i++<<": "<<solve(s)<<endl;
cin>>s;
    }
}
If you find something wrong or have any question about the solution then comment down below, you can also contact us using  contact form.