求助!!!!

#include<cstdio>
using namespace std;
int s[200001],head[51],rear[51],c[200001],pr[200001],qu[51][200001];
int main()
{
int n,k,p,ans;
scanf("%d%d%d",&n,&k,&p);
s[0]=0;
for(int i=0;i<=k-1;i++)
{
head[i]=0;
rear[i]=0;
}
for(int i=1;i<=n;i++)
{
scanf("%d%d",&c[i],&pr[i]);
if(pr[i]<=p)
{
s[i]=s[i-1]+1;
}
else
{
s[i]=s[i-1];
}
rear[c[i]]++;
qu[c[i]][rear[c[i]]]=i;
}
ans=0;
for(int i=0;i<=k-1;i++)
{
for(int j=2;j<=rear[i];j++)
{
bool flag=false;
if(s[qu[i][j]]-s[qu[i][j-1]]>=2||(s[qu[i][j]]-s[qu[i][j-1]]==1&&s[qu[i][j]]-s[qu[i][j]-1]==0))
{
flag=true;
ans=ans+(j-head[i]-1)*(rear[i]-j+1);
head[i]=j-1;
}
if(flag==false&&j==rear[i])
{
if(s[qu[i][j]]-s[qu[i][j]-1]==1)
{
ans=ans+(j-head[i]-1)*(rear[i]-j+1);
}
}
}
}
printf("%d",ans);
return 0;
}
我大概的意思就是先开颜色的队列50个,把颜色相同的放一块,再开一个前缀和储存到i位置之前有多少个合适的咖啡馆,然后在每个队列里找如果qu【j】与qu【j-1】之间有合适的咖啡馆就把用这个馆能构造的都求出来,然后把队头提到那个位置代表之前的都不能构组了最后特别处理一下最后一个,我想的是:如果把咖啡馆在元素j上的情况单独列出用j-1到i之前做就清楚多了,但是不知道怎么了总是错
感谢大神相助!!!!

2 条评论

  • @ 2016-11-02 20:52:11

    谢,不过我已经a了

  • @ 2016-09-10 11:24:00
    #include<stdio.h>
    int n,k,p;
    int s[51];//i前 j色 客栈数
    int last_pos[51];//j色 最后一个客栈
    int c[51];//j色 可行方案数 
    long long ans;
    int main()
    {
        scanf("%d%d%d",&n,&k,&p);
        int m=0;
        for(int i=1;i<=n;i++)
        {
            int col,cost;
            scanf("%d%d",&col,&cost);
            if(cost<=p) m=i;
            if(m>=last_pos[col]) c[col]=s[col];
            ans+=c[col];
            last_pos[col]=i;
            s[col]++;
        }
        printf("%lld",ans);
        return 0;
    }
    
    
  • 1

信息

ID
1737
难度
6
分类
数据结构 | 单调队列 点击显示
标签
递交数
3860
已通过
1162
通过率
30%
被复制
9
上传者