寻找zcmu(upper_bound算法)_2013: 寻找zcmu-程序员宅基地

技术标签: STL  

2013: 寻找zcmu

Time Limit: 1 Sec   Memory Limit: 128 MB
Submit: 466   Solved: 75
[ Submit][ Status][ Web Board]

Description

Input

 多组数据  
每组数据包含一个字符串

 1 <= n <= 100000

Output

 输出一个整数表示最少需要删除的字符数,若不存在则输出"-1"。

Sample Input

zcmu
umcz
zzccmmuuaa

Sample Output

0
-1
2






题解:
找出所有z的位置,有几个z就枚举几次,每次枚举借用upper_bound算法,返回指向第一个大于z位置的迭代器,若没有则返回指向最后一个位置加+1的迭代器
遍历的时候要用ans[i],不然超时,可能是strlen时间耗时长,要用ans[i]
#include<iostream>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
 
#define inf  100010
const int INF = 0x3f3f3f3f;
 
using namespace std;
 
vector< int >z, c, m, u;
int numz, numc, numm, numu;
int main()
{
     char ans[inf];
     int i;
     while ( ~ scanf ( "%s" , ans)){
       for (i = 0; ans[i] ; i++) {
           if (ans[i] == 'z' ) z.push_back(i);
           if (ans[i] == 'c' ) c.push_back(i);
           if (ans[i] == 'm' ) m.push_back(i);
           if (ans[i] == 'u' ) u.push_back(i);
       }
         int an = INF;
         bool flag = false ;
     for ( int i = 0; i < ( int )z.size(); i++) {
       int p1 = upper_bound(c.begin(),c.end(),z[i]) - c.begin();
       if (p1 == c.size()) break ;
       int p2 = upper_bound(m.begin(),m.end(),c[p1]) - m.begin();
       if (p2 == m.size()) break ;
       int p3 = upper_bound(u.begin(),u.end(),m[p2]) - u.begin();
       if (p3 == u.size()) break ;
       flag = 1;
       //cout<<"p1 = "<<p1<<"p2 = "<<p2<<"p3 = "<<p3<<endl;
       if (an > u[p3] - z[i] - 3)
         an = u[p3] - z[i] - 3;
     }
        printf ( "%d\n" , flag ? an : -1);
        z.clear();
        c.clear();
        u.clear();
        m.clear();
     }
     return 0;
}


版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/dreamjay1997/article/details/78778012

智能推荐

CVPR2022 | 医学图像分析中基于频率注入的后门攻击-程序员宅基地

文章浏览阅读775次。点击下方卡片,关注“CVer”公众号AI/CV重磅干货,第一时间送达点击进入—>CV微信技术交流群本工作由京东探索研究院和西北工业大学联合完成,已经被CVPR2022接收。在本文中我们提出了一个基于频域信息注入的后门攻击方法(Frequency-Injection based Backdoor Attack,FIBA)。具体来说,我们设计了一个频域触发器,通过线..._频域 cvpr

【活体检测】人脸活体检测、红外人脸数据集整理_casia nir database-程序员宅基地

文章浏览阅读2.2w次,点赞10次,收藏78次。此篇博客主要整理人脸活体检测的数据集。目前人脸活体攻击的方式主要有:照片打印、视频回放攻击、3D人脸面具等。因此数据集也是根据这些攻击方式制作的。一共整理了11个活体检测的数据集。此外还整理了6个红外人脸数据集。活体检测数据集红外数据:IDIAP:msspoof: Multispectral-Spoof Database1、NUAAhttp://parnec.nuaa.edu.cn/..._casia nir database

Python爬虫基本流程梳理:构造请求头、发起请求、json格式数据解码转码、读写CSV文件——基于AJAX网页爬虫_open('result.csv',mode = 'w')-程序员宅基地

文章浏览阅读1.1k次。构造请求头、发起请求、获取数据import csvurl=urlheaders = { "User-Agent": "Mozilla/5.0 (Macintosh; Intel Mac OS X 10_14_0) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/70.0.3538.110 Safari/537.36"}params =..._open('result.csv',mode = 'w')

反射和注解-程序员宅基地

文章浏览阅读171次。什么是反射?JAVA反射机制是在运行状态中,对于任意一个类,都能够知道这个类的所有属性和方法;对于任意一个对象,都能够调用它的任意一个方法和属性;这种动态获取的信息以及动态调用对象的方法的功能称为java语言的反射机制。Java获取反射的三种方法:1.通过new对象实现反射机制2.通过路径实现反射机制3.通过类名实现反射机制public class Get { //获取反射机制三种方式 public static void main(String[] args) throws C_反射和注解

Xcode7新功能_xocde 7新特性-程序员宅基地

文章浏览阅读1.3k次。重要:这只是开发中API或技术的一个初步文档。苹果提供这些信息来帮助你在苹果产品上采用这些技术和编程界面。这些信息可能发生变化,根据这个文档实现的软件必须在最终的操作系统软件和最终的文档上测试。本文档的新版本可能用来作为未来API或技术的beta版。Xcode是一个完整的开发工具,用于在苹果手表,ipad,iPhone和Mac创建应用程序。Xcode开发工具包涵分析工具、模拟器以及watchO_xocde 7新特性

PIL imagefont文字加边框_pil.imagefont shadow-程序员宅基地

文章浏览阅读4.4k次,点赞3次,收藏10次。使用pil给图片中的文字加个边框,像这样真的是找了很久才找到的,后来在https://stackoverflow.com/questions/41556771/is-there-a-way-to-outline-text-with-a-dark-line-in-pil中简单粗暴地解决了问题,直接上代码from PIL import Image,ImageDraw,ImageFont..._pil.imagefont shadow

随便推点

yarn、npm命令简单比较_yarn 是node包带的吗-程序员宅基地

文章浏览阅读136次。1.概要Yarn:是由Facebook、Google、Exponent 和 Tilde 联合推出了一个新的 JS 包管理工具。npm:是node自带的包管理工具。2. yarn、npm命令简单比较npm yarn 说明 npm init yarn init 初始化某个项目 npm install/link yarn install/link..._yarn 是node包带的吗

YDOOK: cannot be loaded because running scripts is disabled on this system. For more information-程序员宅基地

文章浏览阅读601次。YDOOK:cannot be loaded because running scripts is disabled on this system. For more information YDOOK JYLin1. 解决方案:以管理员方式身份运行 win10 poershell:2. 输入:set-ExecutionPolicy RemoteSigned3. 进入 shell 对话框: 输入 Y:4. 回车:5. 重新使用 npm 脚本创建 vue 项目:成功!_cannot be loaded because running scripts is disabled on this system. for mor

使用 javax.tools 创建动态应用程序_使用javax.tool创建应用程序-程序员宅基地

文章浏览阅读1.4k次。使用 javax.tools 创建动态应用程序 理解并使用 javax.tools.JavaCompiler 构建动态应用程序 _使用javax.tool创建应用程序

编译安装Dropbear并测试(步骤说明)-程序员宅基地

文章浏览阅读8.9k次,点赞4次,收藏16次。1.Dropbear简介Dropbear是一款基于ssh协议的轻量sshd服务器,与OpenSSH相比,他更简洁,更小巧,运行起来占用的内存也更少,但他们都是用于实现ssh安全远程登录协议的,系统默认安装有openssh,而dropbear是基于epel源的,需要自己下载安装。 Dropbear特别用于“嵌入”式的Linux(或其他Unix)系统,如无线路由器。 本文介绍在嵌入式的环境中的安..._dropbear

递归算法求老鼠走迷宫(C语言)_走迷宫c 递归-程序员宅基地

文章浏览阅读9.7k次。/*说明老鼠走迷宫是递回求解的基本题型,我们在二维阵列中使用2表示迷宫墙壁,使用1来表示老鼠的行走路径,试以程式求出由入口至出口的路径。解法老鼠的走法有上、左、下、右四个方向,在每前进一格之后就选一个方向前进,无法前进时退回选择下一个可前进方向,如此在阵列中依序测试四_走迷宫c 递归

【JavaWeb】Spring和它的IOC_java实现spring ioc-程序员宅基地

文章浏览阅读672次。Spring学习了有一段时间了,在学校做的项目以及在京东实习期间也是用到了基于Spring的SpringBoot和SpringCloud。古人云:学而不思则罔。古人又云:温故而知新。所以有必要总结一下Spring的基本知识和核心原理,以便今后更好地使用。 [TOC]Spring的架构 最核心的Spring Core Container(即Spring容器),其他都是可选的。在Spring框架重的_java实现spring ioc