站外题求助大佬!
  • 板块学术版
  • 楼主wjx38223
  • 当前回复9
  • 已保存回复9
  • 发布时间2023/10/11 16:29
  • 上次更新2023/11/2 14:29:31
查看原帖
站外题求助大佬!
902704
wjx38223楼主2023/10/11 16:29

悬关,感谢大佬!!!

等串(wait)

题目描述

若一个字符串中,所有出现的字符的数量相等,则称这个字符串为 wait 串。

给定仅含字符 l , r的字符串 s,你需要求出其中最长的 wait 串的长度。

输入格式

第一行一个整数 nn,表示 s 的长度。

第二行一个长度为 nn 的字符串 s。

输出格式

输出仅一行,即 s 中最长的 wait 串的长度。

样例 #1

样例输入 #1

10
lllrrlrlll

样例输出 #1

6

本人的代码:

//85pts, 剩下15分都是WA
#include<bits/stdc++.h>
using namespace std;
long long sum[5000100];
unordered_map<long long,int> sum2;
long long n;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n;
	for(int i = 1; i<=n; i++){
		char p;
		cin >> p;
		sum[i] = sum[i-1];
		if(p=='l'){
			sum[i]++;
		}else if(p=='r'){
			sum[i]--;
		}
		sum2[sum[i]] = -1;
	}
	sum2[0] = 0;
	long long ans = 0;
	for(int i = 1; i<=n; i++){
		//cout << ans << endl;
		//cout << sum[i] << " ";
		if(sum2[sum[i]]!=-1){
			sum2[sum[i]] = i;
		}else{
			ans = max(ans,i-sum2[sum[i]]);
		}
	}
	cout << ans;
	return 0;
}

2023/10/11 16:29
加载中...