教育改变生活

标题: 小马智行-车辆安排 [打印本页]

作者: 一秉 时间: 2020-9-25 15:49
标题: 小马智行-车辆安排
题目描述：目前小马智行已经获得了加州RoboTaxi服务的许可，意味着小马智行已经可以在加州向所有的公众提供服务。
于是在未来的某一天，小马智行在加州已经拥有了N辆自动驾驶车辆可以面向公众服务，这些车总共有26种颜色，颜色分别为小写字母a到z。现在已知在Pony的服务系统PonyPilot中，总共有M个乘客正在排队，其中每个乘客也有各自的车辆颜色偏好,颜色范围也是a到z。
现在运营小P突然有了一个奇怪的想法：小P想知道总共有多少个位置连续的子队列，能够满足现有的所有车辆可以在同一时刻把子队列中的乘客同时接上乘客喜爱的颜色的车。注意每个车辆只能接一个乘客，且车的颜色要恰好是乘客喜欢的颜色。

代码实现（C++ by今其智乃反不能及）：
#include<iostream>
#include<cstring>
#include<cstdio>

using namespace std;

int n,m;
int Car[30],Peo[30];

char C[1000010],P[1000010];

bool Check()
{
for(int i=0;i<26;i++)
{
      if(Car[i]<Peo[i])
      {
         return false;
      }
}
return true;
}

int main()
{
scanf("%d%d",&n,&m);
scanf("%s%s",C,P);
int Cs=strlen(C),Ps=strlen(P);
for(int i=0;i<Cs;i++)
{
      ++Car[C[i]-'a'];
}
for(int i=0;i<Ps;i++)
{
      P[i]-='a';
}
int lp=0,rp=0;
long long ans=0;
++Peo[P[0]];
while(lp<Ps&&rp<Ps)
{
      if(Check())
      {
         ans+=rp-lp+1;//排序组合的要点
         ++rp;
         ++Peo[P[rp]];
      }
      else
      {
         --Peo[P[lp]];
         ++lp;
         if(lp>rp)
         {
            ++rp;
            ++Peo[P[rp]];
         }
      }
}
printf("%lld",ans);
return 0;
}

欢迎光临教育改变生活 (http://bbs.goldoar.com/)