Codeforces-data+structures（1）

丝毫没有感觉到用到数据结构，可能是太水了

Hotelier

题意：酒店里有10个房间和两个门（左边和右边），进门后先安排最近的房间，客人可以随时离开房间。给定一个长度为n的字符串，L表示客人从左边的门进入，R表示客人从右边的门进入，0~9表示该房间的客人离开房间。求最后房间的状态。

思路：直接模拟即可。对于每一个L或R，分别从开始或结尾遍历到第一个为没有人的房间；对于数字，直接让该a[i]=0即可。

代码：

#include<bits/stdc++.h>

using namespace std;

const int maxn=1e6+7;

int a[maxn],n;

int main(){
    cin>>n;
    string s;cin>>s;
    for(int i=0;i<s.size();i++){
        if(s[i]=='L'){
            for(int j=0;j<10;j++)
                if(!a[j]){
                    a[j]=1;
                    break;
                }
        }
        else if(s[i]=='R'){
            for(int j=9;j>=0;j--)
                if(!a[j]){
                    a[j]=1;
                    break;
                }
        }
        else a[s[i]-'0']=0;
    }
    for(int i=0;i<10;i++) cout<<a[i];
    return 0;
}

Polycarp Training

题意：给定一个长度为n的数组，要求第i天的最低需求为i，问用这个数组里的数最多能够满足多少天的需求。

思路：贪心的思想，a[i]小的先用，记录一下就可以了

代码：

#include<bits/stdc++.h>

using namespace std;

const int maxn=1e6+7;

int a[maxn],n;

int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    int res=1;
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++) 
        if(a[i]>=res) res++;
    cout<<res-1;
    return 0;
}

Sereja and Suffixes

题意：给定一个数组，每一组询问都求x~n中不同的数的个数。

思路：直接暴力肯定超时，我们可以维护一个后缀s[i]表示从i~n不同的数的个数，这样就可以O（1）查询了。总的时间复杂度是O（n+m）;

代码：

#include<bits/stdc++.h>

using namespace std;

const int maxn=1e6+7;

int a[maxn],s[maxn],q[maxn];
int n,m;

int main(){
    cin>>n>>m;
    s[n+1]=0;
    set<int>ss;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=n;i;i--)
        if(ss.count(a[i])==0){
            ss.insert(a[i]);
            s[i]=s[i+1]+1;
        }
        else s[i]=s[i+1];
    for(int i=1;i<=m;i++){
        cin>>q[i];
        cout<<s[q[i]]<<endl;
    }
    return 0;
}