Codeforces Round #704 (Div. 2) C. Maximum width 贪心_.maximum width(贪心、双指针)

原题链接：https://codeforces.ml/contest/1492/problem/C

题意

有s和t两个字符串，有一个序列p1，p2…pm满足spi = ti，现在求pi - pi-1的最大值

分析

因为一个ti可以对应多个位置，因此考虑贪心最优的策略。但要注意p是上升的序列，所以用双指针保证不减。

正着走一遍可以算出每个ti位置可以取到的最小值，然后再倒着走一遍算出可以取到的最大值。

那么最大的差值就是当前数的最大值减前一个数的最小值，再走一遍取max即可。

Code

#include <bits/stdc++.h>
using namespace std;
//#define ACM_LOCAL
#define fi first
#define se second
#define il inline
#define re register
typedef long long ll;
typedef pair<int, int> PII;
typedef unsigned long long ull;
const int N = 5e5 + 10;
const int M = 1e6 + 10;
const int INF = 1e9 + 5;
const double eps = 1e-5;
const int MOD = 998244353;

void solve() {
    int n, m; cin >> n >> m;
    string s1, s2; cin >> s1 >> s2;
    int now = 0;
    vector<int> pre(m+1), back(m+1);
    for (int i = 0; i < s1.size(); i++) {
        if (now < s2.size() && s1[i] == s2[now]) {
            pre[now] = i;
            now++;
        }
    }
    now = s2.size() - 1;
    for (int i = s1.size() - 1; i >= 0; i--) {
        if (now >= 0 && s1[i] == s2[now]) {
            back[now] = i;
            now--;
        }
    }
    int ans = 0;
    for (int i = 1; i < m; i++) ans = max(ans, back[i] - pre[i-1]);
    cout << ans << endl;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
#ifdef ACM_LOCAL
    freopen("input", "r", stdin);
    freopen("output", "w", stdout);
#endif
    solve();
}

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
39
40
41
42
43
44
45
46
47
48
49
50