Description
JOIOJI桑是JOI君的叔叔。“JOIOJI”这个名字是由“J、O、I”三个字母各两个构成的。
最近,JOIOJI桑有了一个孩子。JOIOJI桑想让自己孩子的名字和自己一样由“J、O、I”三个字母构成,并且想让“J、O、I”三个字母的出现次数恰好相同。
JOIOJI桑家有一份祖传的卷轴,上面写着一首长诗,长度为N,由“J、O、I”三个字母组成。JOIOJIさん想用诗中最长的满足要求的连续子串作为孩子的名字。
现在JOIOJI桑将这首长诗交给了你,请你求出诗中最长的、包含同样数目的“J、O、I”三个字母的连续子串。
Input
第一行一个正整数N,代表这首长诗的长度
接下来一行一个长度为N的字符串S,表示这首长诗,保证每个字符都是“J、O、I”三个字母中的一个
Output
输出一行一个正整数,代表最长的包含等数量“J、O、I”三个字母的最长连续子串的长度。如果不存在这样的子串,输出0
Sample Input
10
JOIIJOJOOI
JOIIJOJOOI
Sample Output
6
HINT
选择“IIJOJO”这个子串,长度为6,包含“J、O、I”三个字母各2个,这是最长的满足要求的子串。
1<=N<=2*10^5
Source
JOI 2013~2014 春季training合宿 竞技3 By PoPoQQQ
Solution
设J[i]为前i个字符中J的个数,O[i]为前i个字符中O的个数,I[i]为前i个字符中I的个数。
现在要求区间[L+1,R]使得区间内J,O,I字符个数相等。
即J[R]-J[L]=O[R]-O[L]=I[R]-I[L]
变式可得J[R]-O[R]=J[L]-O[L],O[R]-I[R]=O[L]-I[L]。
所以我们可以令数组JO[i]=J[i]-O[i],OI[i]=O[i]-L[i],然后通过排序线扫来求得R-L的最大值。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int MAXN=200100; int n,J[MAXN],O[MAXN],I[MAXN]; char s[MAXN]; struct node{int JO,OI,tot;}a[MAXN]; bool cmp(node a,node b) { if (a.JO<b.JO||(a.JO==b.JO&&a.OI<b.OI)||(a.JO==b.JO&&a.OI==b.OI&&a.tot<b.tot)) return true; return false; } int main() { scanf("%d",&n); scanf("%s",s); J[0]=O[0]=I[0]=0; for (int i=1;i<=n;i++) { if (s[i-1]=='J') J[i]=J[i-1]+1;else J[i]=J[i-1]; if (s[i-1]=='O') O[i]=O[i-1]+1;else O[i]=O[i-1]; if (s[i-1]=='I') I[i]=I[i-1]+1;else I[i]=I[i-1]; } for (int i=1;i<=n;i++) a[i].JO=J[i]-O[i],a[i].OI=O[i]-I[i],a[i].tot=i; n++;a[n].JO=a[n].OI=a[n].tot=0; sort(a+1,a+n+1,cmp); int last=1,Max=0; for (int i=2;i<=n+1;i++) { if (a[i].JO==a[last].JO&&a[i].OI==a[last].OI&&i!=n+1) continue; if (a[i-1].tot-a[last].tot>Max) Max=a[i-1].tot-a[last].tot; last=i; } printf("%d\n",Max); return 0; } |
MAP乱搞哈哈哈
为什么我的用户名变小写了。。。
2153424 yzdwg 4236 Accepted 6368 kb 1192 ms C++/Edit 825 B 2017-07-07 21:46:01