题解 P3519 【[POI2011]ROZ-Difference】

bzy369258147 · 2019-03-09 11:07:23 · 题解

不同的解法 : 更简单的思想.

前置知识: 需要对归并排序的实现有所了解 ).

由于这个题目的字符集大小只有26,我们显然可以枚举出现次数最多与最少的字符是什么。然后把这两个字符离散出来问题就变成了只有1与-1且强制选取至少一个-1的最大连续子段和问题。

然后关于离散，我们显然可以用vector把每中字符的出现位置记录下来。然后用类似归并的方法求解即可。

关于强制选取至少一个-1的最大连续子段和问题,我们可以先把答案预设为-1然后到第一个-1时不减即可解决。

由于每种字符作为最大与最小总共被枚举52次，所有字符的数量和为n

所以时间复杂度为 O(52n)

空间复杂度 O(n)

以下是代码:

#include<bits/stdc++.h>
using namespace std;

vector<int> bin[26];
char s[1000005]; int n;

int ans = 0;

int main(){
    cin >> n >> s;
    for(int i = 1;i <= n;i ++) bin[ s[i - 1] - 'a' ].push_back(i);
    for(int i = 0;i < 26;i ++) if( bin[i].size() ) 
        for(int j = 0;j < 26;j ++) if( bin[j].size() ) if( i ^ j ) {
            int pt1 = 0, pt2 = 0, fir = 0;
            int all = -1;
            while( pt1 < bin[i].size() or pt2 < bin[j].size() ) {
                int tp1 = pt1 == bin[i].size() ? 1e9 : bin[i][pt1];
                int tp2 = pt2 == bin[j].size() ? 1e9 : bin[j][pt2];
                if( tp1 < tp2 ) all ++, pt1 ++;
                if( tp1 > tp2 ) { if( fir ) all --; pt2 ++; fir = 1; }
                if( all < 0 ) all = -1, fir = 0;
                ans = max( ans, all );
            }
        }
    cout << ans;
    return 0;
}