本文主要是介绍牛客练习赛24。C-PH试纸(思维),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目描述
PH试纸,是一种检测酸碱度的试纸,试纸红色为酸性,蓝色为碱性。
HtBest有一个PH试纸,试纸被分成了n段,每一段都可以被染色成红色或者蓝色,WHZ在试纸的每一段上都染为一种颜色,HtBest有m个询问,对于每个询问,Ta想知道某种颜色第qi次在什么地方出现。
输入描述:
第一行有两个正整数n,m。 第二行有n个字母(‘R’或’B’),每个第i个字母表示PH试纸第i段的颜色。 接下来m行,第i行有一个大写字母 ci(‘R’或’B’)和一个正整数qi ,用空格隔开,表示查询颜色ci 第qi 次出现的位置。
输出描述:
共m行,第i行一个整数,表示查询结果,若颜色ci出现次数少于qi次,则输出-1,否则输出颜色qi第ci次出现的位置。
示例1
输入
复制
2 2 RB R 1 B 1
输出
复制
1 2
示例2
输入
复制
2 2 BB R 1 B 2
输出
复制
-1 2
示例3
输入
复制
3 3 BRB B 1 B 2 R 1
输出
复制
1 3 2
备注:
对于100%的测试数据: 1 ≤ n, m ≤ 1000000 所有输入数据不超过1000000。 数据量较大,注意使用更快的输入输出方式。
思路:因为只有两种颜色,所以用数组存一下次数和位置就行了。
#include <bits/stdc++.h>
using namespace std;
#define maxn 1000005
#define ll long long
char str[maxn];
int R[maxn], B[maxn];
int main()
{int n, m, i, a, b;scanf("%d%d%s", &n, &m, str+1);a = b = 0;for(i = 1; i <= n; i++){if(str[i] == 'R')R[++a] = i;elseB[++b] = i;}while(m--){scanf("%s%d", str, &b);if(str[0] == 'R')printf("%d\n", R[b] == 0 ? -1 : R[b]);elseprintf("%d\n", B[b] == 0 ? -1 : B[b]);}return 0;
}
这篇关于牛客练习赛24。C-PH试纸(思维)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!