最大值情况 CodeForces - 1321C

    科技2024-08-22  26

    题目大意: 刚刚折腾完增加字符的操作,现在就来搞删除吧,给你一个由小写字母组成的字符串s,现在要做删除操作,不过不能随便删,要求是某个字母的两边,存在一个字母序小1的字母的时候,它就可以删除,例如说,“cabcb”,第二个c旁边有b就可以删除它,剩下"cabb",然后中间的b旁边有a,删除它,剩下"cab",再删一个b,最后得到"ca",一共删除了3个字符 一开始wa的思想,想着从头到尾遇见前一个比第二个大一的就删除第一个或者遇见逐渐增大的查询到最大的那一个数就删除,每当删除就从头开始,但是这个题让输出最多可删除的个数,最开始的想法看着挺靠谱,但是貌似跟最多并没有什么联系,提交之后果然wa了,这个题是让你删除一个大的字母,只要是大的就可能被删除,于是从z开始到b从大到小一个一个搜索是否能被删除,有点贴近暴力的感觉。此题解

    #include <bits/stdc++.h> typedef long long ll; const int MAX=0x7fffffff; using namespace std; int n; vector<int> s; int main() { cin>>n; char a; for(int i=0;i<n;i++){ cin>>a; s.push_back(a-'a'+1); } int blen=s.size(); vector<int>::iterator it=s.begin(); for(int d=26;d>1;d--){ for(int i=0;i<s.size();i++){ if(s[i]==d){ if(i>=1&&s[i-1]==d-1){ s.erase(it+i); i=0; } else if(i<s.size()-1&&s[i+1]==d-1){ s.erase(it+i); i=0; } } } } cout<<blen-s.size()<<endl; return 0; }
    Processed: 0.010, SQL: 8