STL初步|20201030|

Where is the Marble? UVA-10474

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;
const int maxn=100000;
int arr[maxn];
int main()
{
    int n,q,casenum=1;
    while(~scanf("%d%d",&n,&q) && n){
        printf("CASE# %d:\n",casenum++);
        for(int i=0;i<n;i++) scanf("%d",&arr[i]);
        sort(arr,arr+n);
        while(q--){
            int x;scanf("%d",&x);
            int p=lower_bound(arr,arr+n,x)-arr;
            if(arr[p]==x) printf("%d found at %d\n",x,p+1);
            else printf("%d not found\n",x);
        }
    }
    return 0;
}

sort()

两参数默认从小到大，三参数cmp函数写bool（参考ref内例子）

参考：cpp_ref

lower_bound

在first和last中的前闭后开区间进行二分查找，返回大于或等于val的第一个元素位置。如果所有元素都小于val，则返回last的位置

参考：cpp_ref

The Blocks Problem UVA - 101

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
int n;
const int maxn=30;
vector<int> pile[maxn];

void find_block(int a,int &p,int &h){
    for(p=0;p<n;p++){
        for(h=0;h<pile[p].size();h++){
            if(pile[p][h]==a) return;
        }
    }
}
void clear_above(int p,int h){
    for(int i=h+1;i<pile[p].size();i++){
        int b=pile[p][i];
        pile[b].push_back(b);
    }
    pile[p].resize(h+1);
}

void pile_onto(int p,int h,int p2){
    for(int i=h;i<pile[p].size();i++){
        pile[p2].push_back(pile[p][i]);
    }
    pile[p].resize(h);
}

void print(){
    for(int i=0;i<n;i++){
        printf("%d:",i);
        for(int j=0;j<pile[i].size();j++){
            printf(" %d",pile[i][j]);
        }
        printf("\n");
    }
}

int main()
{
    int i;scanf("%d",&n);
    string str1,str2;
    int a,b;
    for(i=0;i<n;i++) pile[i].push_back(i);
    while(cin>>str1){
        if(str1=="quit") break;
        cin>>a>>str2>>b;
        int pa,pb,ha,hb;
        find_block(a,pa,ha);
        find_block(b,pb,hb);
        if(pa==pb) continue;
        if(str2=="onto") clear_above(pb,hb);
        if(str1=="move") clear_above(pa,ha);
        pile_onto(pa,ha,pb);
    }
    print();
    return 0;
}

vector

向量（Vector）是一个封装了动态大小数组的顺序容器（Sequence Container）。跟任意其它类型容器一样，它能够存放各种类型的对象。可以简单的认为，向量是一个能够存放任意类型的动态数组。

参考：C++ vector 容器浅析 | cpp_ref

Andy’s First Dictionary UVA - 10815

#include <iostream>
#include <set>
#include <sstream>
#include <string>
using namespace std;
set<string> dict;

int main()
{
    string s,buf;
    while(cin>>s){
        for(int i=0;i<s.length();i++){
            if(isalpha(s[i])) s[i]=tolower(s[i]);
            else s[i]=' ';
        }
        stringstream ss(s);
        while(ss>>buf) dict.insert(buf);
    }
    for(set<string>::iterator it=dict.begin();it!=dict.end();++it)
        cout<<*it<<"\n";
    return 0;
}

set

set是STL中的常见容器，set中不允许有重复元素，并且set中的元素是排好序的

参考：cpp_ref | C++set用法详解 | C++中set的用法

stringstream

参考：cpp_ref | stringstream常见用法介绍

set<string>::interator
迭代器，类似于指针
参考：c++迭代器（iterator）详解