- 选择客栈
- 2015-12-14 20:25:41 @
#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 条评论
-
shangyuxuan LV 8 @ 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