专栏首页奇妙的算法世界codeforces 1321C(贪心)

codeforces 1321C(贪心)

题意描述

思路

每次删除字典序最大的字母即可,因为删除字典序最大的字母不会影响到其他字母。每次删除后更新字符串

AC代码

#include<bits/stdc++.h>
#define x first
#define y second
#define PB push_back
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) begin(a),end(a)
#define rep(x,l,u) for(ll x=l;x<u;x++)
#define rrep(x,l,u) for(ll x=l;x>=u;x--)
#define sz(x) x.size()
#define IOS ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<char,char> PCC;
typedef long long ll;
typedef pair<ll,ll> PLL;
const int N=105;
const int M=1e5+10;
const int INF=0x3f3f3f3f;
const int MOD=1e9+7;
bool st[N];
void solve(){
    int n;
    string s;
    cin>>n>>s;
    string buf=s;
    string res=s;
    sort(all(buf));
    int ans=0;
    int idx=n-1;
    rep(i,0,n){
        mst(st,false);
        rep(j,0,sz(res)){
            if(res[j]==buf[idx]){
                if(j>0 && abs(res[j]-res[j-1])==1 || j<n && abs(res[j]-res[j+1])==1){
                    ans++;
                    st[j]=true;
                }
            }
        }
        string f;
        rep(j,0,sz(res)) if(!st[j]) f+=res[j];
        res=f;
        idx--;
    }
    cout<<ans<<endl;
}
int main(){
    IOS;
    //freopen("test.txt", "r", stdin);
    //freopen("test.txt", "w", stdout);
    //int t;cin>>t;
    //while(t--)
        solve();
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • HDU1024(dp)

    dejavu1zz
  • codeforces 1426D(思维)

    来储存每一步已经存在过的前缀和。如果在某个时刻,发现该前缀和已经出现过或已经为0,则说明需要插入一个足够大的数,也就意味着左边区间内的所有数被擦除,我们可以将s...

    dejavu1zz
  • codeforces 1334C(前缀和)

    dejavu1zz
  • SPOJ HIGH Highways(生成树计数模板题)

    题目链接:https://www.spoj.com/problems/HIGH/en/

    Ch_Zaqdt
  • Java Web Response对象的27个方法及状态码

    response表示HttpServletResponse对象,主要将JSP容器处理后的结果传回到客户端。 ? 网络配图 1、void addCookie(...

    用户1289394
  • 【改革春风吹满地 HDU - 2036 】【计算几何-----利用叉积计算多边形的面积】

    我们都知道计算三角形的面积时可以用两个邻边对应向量积(叉积)的绝对值的一半表示,那么同样,对于多边形,我们可以以多边形上的一个点为源点,作过该点并且过多边形其他...

    _DIY
  • 238. Product of Array Except Self

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/Oct31_Dec25/article/details...

    yesr
  • codeforces 940B(贪心)

    Right now she actually isn’t. But she will be, if you don’t solve this problem.

    dejavu1zz
  • 分治

    什么是分治算法呢? 对于一个规模为n的问题,若该问题可以容易地解决(比如说规模n较小),则直接解决,否则将其分解为k个规模较小的子问题,这些子问题互相独立且与...

    黑白格
  • #define a int[10]与 typedef int a[10]用法

    Daotin

扫码关注云+社区

领取腾讯云代金券