首页 > 试题广场 > 车辆安排
[编程题]车辆安排
  • 热度指数:248 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
目前小马智行已经获得了加州RoboTaxi服务的许可,意味着小马智行已经可以在加州向所有的公众提供服务。
于是在未来的某一天,小马智行在加州已经拥有了N辆自动驾驶车辆可以面向公众服务,这些车总共有26种颜色,颜色分别为小写字母a到z。现在已知在Pony的服务系统PonyPilot中,总共有M个乘客正在排队,其中每个乘客也有各自的车辆颜色偏好,颜色范围也是a到z。
现在运营小P突然有了一个奇怪的想法:小P想知道总共有多少个位置连续的子队列,能够满足现有的所有车辆可以在同一时刻把子队列中的乘客同时接上乘客喜爱的颜色的车。注意每个车辆只能接一个乘客,且车的颜色要恰好是乘客喜欢的颜色。


输入描述:
第一行输入两个数字N,M。N代表车辆数,M代表乘客人数。

第二行输入一个字符串A,长度为N,表示每辆车的颜色。

第三行输入一个字符串B,长度为M,表示当前排队的乘客分别喜欢的车的颜色。

其中,1<=N<=1000000, 1<=M<=1000000。


输出描述:
输出一个数,即总共满足要求的子队列数。
示例1

输入

4 6
pony
pponyy

输出

12

说明

满足的子队列分别为([]内为子队列对应的下标区间):

p, [0, 0]
p, [1, 1]
o, [2, 2]
po, [1, 2]
n, [3, 3]
on, [2, 3]
pon, [1, 3]
y, [4, 4]
ny, [3, 4]
ony, [2, 4]
pony, [1, 4]
y, [5, 5]
示例2

输入

2 2
ab
ba

输出

3

说明

满足的子队列分别为([]内为子队列对应的下标区间):

b, [0, 0]
ba, [0, 1]
a, [1, 1]
//滑动窗口 + Cascading


import java.util.*;
 
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String[] temp = sc.nextLine().split(" ");
        int numC = Integer.parseInt(temp[0]);
        int numP = Integer.parseInt(temp[1]);
        String cars = sc.nextLine();
        String people = sc.nextLine();
         
        int left = 0;
        int right = 0;
        int[] tableC = new int[26];
        for(int i = 0; i<numC; i++){
            tableC[cars.charAt(i)-'a']++;
        }
        int[] tableP = new int[26];
        long res = 0;
        while(right<numP){
            int index = people.charAt(right)-'a';
            tableP[index]++;
            if(tableP[index]<=tableC[index]){
                res+=right-left+1;
            }
            else{
                while(left<=right&&tableP[index]>tableC[index]){
                    tableP[people.charAt(left)-'a']--;
                    left++;
                }
                res+= right-left+1;
            }
            right++;
        }
        System.out.println(res);
    }
}


发表于 2020-10-17 13:48:32 回复(0)
简单的尺取法,要注意一下排序组合的问题(具体看注释
#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;
}

时间复杂度为O(nlogn)

发表于 2020-07-21 09:37:40 回复(0)
#include<bits/stdc++.h>
using namespace std;
vector<int> sub(vector<int> &a,vector<int> &b){
    vector<int> res(26);
    for(int i = 0;i<26;i++) res[i] = a[i] - b[i];
    return res;
}
int Cnt(vector<int> &a){
    int res = 0;
    for(auto x:a) res += x;
    return res;
}
int main(){
    vector<int> c(26,0);
    int N,M;
    cin>>N>>M;
    char cc;
    for(int i = 0;i<N; i++){
        cin>>cc;
        c[cc-'a']++;
    }
    vector<vector<int>> cnt;//每个位置每种车喜欢的乘客数
    vector<vector<int>> ind(26);//记录每种字符索引
    vector<int> tmp(26,0);
    vector<int> Zero(26,0);
    vector<int> curr(26,0);
    long long ans = 0;
    for(int i = 0; i < M; i++){
        cin>>cc;
        int cur = cc - 'a';
        tmp[cur]++;
        cnt.push_back(tmp);
        curr[cur]++;
        if(curr[cur] > c[cur]){
            if(c[cur] == 0) curr = Zero;
            else {
                int s = ind[cur].size();
                curr = sub(cnt[i],cnt[ind[cur][s-c[cur]]]);
            }
        }
        ind[cur].push_back(i);
        ans += Cnt(curr);
    }
    cout<<ans;
    return 0;
}

发表于 2020-08-20 21:21:16 回复(0)
//*****通过40%******超时******
#include <iostream>
#include <unordered_map>
#include <string>
#include <string.h>

using namespace std;
int main(){     unordered_map<char, int> map;     for (int i=0;i<26;i++)  map['a'+i] = 0;     int n,m;     cin>>n>>m;             //n:车辆数, m:乘客人数     string str_car, str_pas;                 cin>>str_car;     cin>>str_pas;          int result = 0;     for(char i:str_car)  map[i]++;      unordered_map<char, int> map_copy = map;          for(int i=0;i<m;i++){         map_copy = map;         for(int j=0;j<n;j++){             if(--map_copy[str_pas[i+j]] < 0)  break;             result++;         }//for car     }//for passager          cout<<result;          return 0;
}    

//******通过100%*******
//int->long long
//暴搜+跳过某些情况

#include <iostream>
#include <unordered_map>
#include <string>
#include <string.h>
 
using namespace std;
int main(){
    unordered_map<char, int> map;
    for (int i=0;i<26;i++)  map['a'+i] = 0;
    int n,m;
    cin>>n>>m;             //n:车辆数, m:乘客人数
    string str_car, str_pas;         
    cin>>str_car;
    cin>>str_pas;
     
    long long result = 0;
    for(char i:str_car)  map[i]++; 
    unordered_map<char, int> map_copy = map;
    int temp=0;
     
    for(int i=0;i<m;i++){
        // map_copy = map;
        for(int j=temp;j<n;j++){
            map_copy[str_pas[i+j]]--;
            if(map_copy[str_pas[i+j]] < 0 && j-1>=0)   {temp = j-1; map_copy[str_pas[i]]++ ; map_copy[str_pas[i+j]]++;result+=j-1; break;}
            // else if(map_copy[str_pas[i+j]] < 0 && j-1>=0)   {temp = 0; map_copy[str_pas[i]]++ ; break;}
            else if(map_copy[str_pas[i+j]] < 0 && j  >=0)   {temp = 0; map_copy=map ; break;}
            else if(j==n-1)  {temp=j;map_copy[str_pas[i]]++;result+=j;}   
            result++;
            //cout<<i<<"to"<<i+j<<":"<<result<<endl;
        }//for car
    }//for passager
     
    cout<<result;
     
    return 0;
}

编辑于 2020-07-21 14:43:29 回复(0)