WA Code:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
#include <iostream> #include <map> #include <string> using namespace std; map<char,int> m,np; //vector<char> v; int main() { string str; int cnt; int kase=1; while(cin>>str) { if(str=="end") break; cnt=1; np.clear(); m.clear(); for(int i=0;i<str.size();i++) { if(m[str[i]]<(i+1)) m[str[i]]=i+1; } for(map<char,int>::iterator ii=m.begin();ii!=m.end();++ii) { cout<<ii->first<<" "<<ii->second<<"\n"; int pos=ii->second; char c=ii->first; int f=0; for(int i=0;i<pos;i++) { if(str[i]<c && np[str[i]]==0) { np[str[i]]=1; if(f==0) cnt++; f=1; } } } cout<<"\n\n"; cout<<"Case "<<kase++<<": "; cout<<cnt<<"\n"; } return 0; } |
Idea
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. 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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
#include <iostream> #include <stack> #include <vector> #include <string> using namespace std; vector<stack<char> > container; string s; int add_next_char(int pos) { stack<char> cargo; for(int i=0;i<container.size();i++) { if(container[i].top()>=s[pos]) { container[i].push(s[pos]); return 0; } //for(int j=0;j<) } //cargo.clear(); cargo.push(s[pos]); container.push_back(cargo); return 1; } int main() { int kase=1; while(cin>>s) { if(s=="end") break; container.clear(); int total=0; for(int i=0;i<s.size();i++) { total+=add_next_char(i); } cout<<"Case "<<kase++<<": "<<total<<"\n"; } return 0; } |