专栏首页HansBug's Lab3016: [Usaco2012 Nov]Clumsy Cows

3016: [Usaco2012 Nov]Clumsy Cows

3016: [Usaco2012 Nov]Clumsy Cows

Time Limit: 1 Sec  Memory Limit: 128 MB

Submit: 91  Solved: 69

[Submit][Status][Discuss]

Description

Bessie the cow is trying to type a balanced string of parentheses into her new laptop, but she is sufficiently clumsy (due to her large hooves) that she keeps mis-typing characters. Please help her by computing the minimum number of characters in the string that one must reverse (e.g., changing a left parenthesis to a right parenthesis, or vice versa) so that the string would become balanced. There are several ways to define what it means for a string of parentheses to be "balanced". Perhaps the simplest definition is that there must be the same total number of ('s and )'s, and for any prefix of the string, there must be at least as many ('s as )'s. For example, the following strings are all balanced:

()

(())

()(()())

while these are not:

)(

())(

((())))

问题描述

给定长度为n的一个括号序列,每次修改可以修改一个位置的括号,若这个括号为’(‘,则修改为’)’,若这个括号为’)’,则修改为’(‘,问最少修改多少个使得原括号序列合法。

其中:

①     ()是合法的;

②     若A是合法的,则(A)是合法的;

③     若AB都是合法的,则AB是合法的。

Input

       一个长度为n个括号序列。

Output

       最少的修改次数。

Sample Input

())(

Sample Output

2 样例说明 修改为()(),其中红色部分表示修改的括号。 数据范围 100%的数据满足:1 <= n <= 100,000。

HINT

Source

Silver

题解:一个很神奇的模拟,感觉自己水水哒

 1 /**************************************************************
 2     Problem: 3016
 3     User: HansBug
 4     Language: Pascal
 5     Result: Accepted
 6     Time:72 ms
 7     Memory:220 kb
 8 ****************************************************************/
 9  
10 var ch:char;s,ans:longint;
11 begin
12      while not(eoln) do
13            begin
14                 read(ch);
15                 if ch='(' then inc(s) else
16                    begin
17                         dec(s);
18                         if s<0 then
19                            begin
20                                 inc(s,2);
21                                 inc(ans);
22                            end;
23                    end;
24            end;
25      ans:=ans+s div 2;
26      writeln(ans);
27 end.

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 3892: [Usaco2014 Dec]Marathon

    3892: [Usaco2014 Dec]Marathon Time Limit: 10 Sec  Memory Limit: 128 MB Submit: 1...

    HansBug
  • 2020: [Usaco2010 Jan]Buying Feed, II

    2020: [Usaco2010 Jan]Buying Feed, II Time Limit: 3 Sec  Memory Limit: 64 MB Subm...

    HansBug
  • 1740: [Usaco2005 mar]Yogurt factory 奶酪工厂

    1740: [Usaco2005 mar]Yogurt factory 奶酪工厂 Time Limit: 5 Sec  Memory Limit: 64 MB ...

    HansBug
  • 数据仓库专题(21):Kimball总线矩阵说明-官方版

    Over the years, I have found that a matrix depiction of the data warehouse plan...

    数据饕餮
  • [Go] gocron源码阅读-go语言的结构体

    结构体类型 type 名字 struct{},下面这段是github.com/urfave/cli包里的代码,声明了一个App的结构体类型

    陶士涵
  • 强文!LEARNING ACTIONABLE REPRESENTATIONS WITH GOAL.. POLICIES

    LEARNING ACTIONABLE REPRESENTATIONS WITH GOAL-CONDITIONED POLICIES

    用户1908973
  • CodeForces 156A Message(暴力)

    A. Message time limit per test 2 seconds memory limit per test 256 megabyt...

    ShenduCC
  • 十大革命性理论(Top 10 revolutionary scientifictheories)中英版(19k字)

    本篇《十大革命性理论》(Top 10 revolutionary scientific theories |Science News)中英文对照版AB,把原文倒...

    秦陇纪
  • 摩斯码编解码器

      今天是1024,程序员节那就干点儿程序员的事情。刚好,记得上高中时候,看过一部电影,无间道,里边黄秋生和梁朝伟用摩斯码通信,瞬间觉得好神秘,好帅气。最近闲来...

    guokun
  • Will Multi-Cloud Become The Ultimate Business Strategy In 2020?

    If we are to sort the cool kids in the business tech world right now, Cloud comp...

    用户7478942

扫码关注云+社区

领取腾讯云代金券