Acwing春季每日一题 3358. 放养但没有完全放养

Acwing春季每日一题 3358. 放养但没有完全放养

思路：

贪心。b字符串中如果出现了逆序或者相等的，那么一定不在一个abc..xyz中，例如 mood 两个o肯定不在同一个abc...xyz中，我们记b中满足性质的个数为cnt，最后的答案就是cnt + 1。

证明贪心的两个性质：

1. A >= B, 且 B可以取到A，那么B就是答案
2. 夹逼定理

这道题中，我们可以把abc..xyzabc...xyz...分成恰好可以完整覆盖牛文的段，那么我么可以把每一个逆序插到一个abc..xyz中，所以 B 可以取到 A，所以B就是答案。

代码：

#include<iostream>
#include<string>
#include<vector>

using namespace std;

int main(){
    string a,b;
    cin>>a>>b;
    vector<int> p(26 + 1);
    for(int i = 0;i < 26;i++) p[a[i] - 'a'] = i;
    int res = 1;
    for(int i = 0;i < b.size();i++){
        if(i && p[b[i] - 'a'] <= p[b[i - 1] - 'a']) res++;
    }
    cout<<res;
    return 0;
}