P1311 选择客栈-白红宇

P1311 选择客栈

阅读量：4353 次

发布时间：2019-06-07

本文共 1401 字，大约阅读时间需要 4 分钟。

枚举右端点

可以发现左右端点中有一个合法的咖啡店就可以了

而且为了让合法的左端点尽量多

咖啡店要尽量靠右

所以可以记录目前最右边的合法咖啡店左边每种颜色的客栈的个数 cnt[ color ]

然后如果更右边有合法的咖啡店，就更新一波 cnt

累计所有右端点的情况

复杂度 O(nk)

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;const int N=5e5+7;int n,k,p;int col[N],val[N],ans;int cnt[57],sum[57];int main(){    cin>>n>>k>>p;    for(int i=1;i<=n;i++)        scanf("%d%d",&col[i],&val[i]);    for(int i=1;i<=n;i++)    {        sum[col[i]]++;//中间数组        if(val[i]<=p)            for(int j=0;j

O(nk)代码

可以发现我们很多时间花在了更新cnt上

每次有咖啡店就把所有的cnt都更新了

但是其实每次我们只要更新当前颜色的cnt就可以了

所以可以记 las[ i ] 表示颜色 i 最右边出现的位置

pos 表示最右边合法的咖啡店的位置

如果 pos >= las[ lolor[r] ] 才更新cnt

复杂度 O(n)

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;const int N=5e5+7;int n,k,p;int col[N],val[N],ans;int cnt[57],sum[57],las[57];int main(){    cin>>n>>k>>p;    for(int i=1;i<=n;i++)        scanf("%d%d",&col[i],&val[i]);    int pos=0;    for(int i=1;i<=n;i++)    {        if(val[i]<=p) pos=i;        if(pos>=las[col[i]]) cnt[col[i]]+=sum[col[i]],sum[col[i]]=0;        las[col[i]]=i;        ans+=cnt[col[i]];        sum[col[i]]++;    }    cout<