Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
欢迎参加IJCAI 2020麻将智能体竞赛,大奖等你拿!Welcome to IJCAI 2020 Mahjong AI competition with amazing prizes! | 北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

算法与证明(revised)

Posted by cavatina2016 at 2020-08-01 15:43:00 on Problem 3991 and last updated at 2020-08-01 23:11:01
In Reply To:算法与证明 Posted by:cavatina2016 at 2020-08-01 01:14:00
设字符串S=[A1 A2 ... AN], Ai(1<=i<=N)为'{'或'}',要用最少的替换操作使S满足要求

贪心算法:
1.设res为最终替换次数
2.设P为一个堆栈,保存未被匹配的'{'的序号,初始为空
3.从A1到AN顺序扫描S
4.如果Ai='{', 则P.push(i)
5.如果Ai='}'且P不为空,则j = P.pop(),让Aj与Ai匹配
6.如果Ai='}'且P为空,则将Ai替换为'{'、P.push(i)、res++
7.如果S扫描完毕后P中还有X个元素,则将栈顶的X/2个序号指向的'{'替换为'}',与栈底的X/2个序号指向的'{'相匹配,同时res += X/2
8.实际代码只要记录P中元素的个数就行了

证明:
1. X为偶数
设a为原字符串中'{'的个数,b为原字符串中'}'的个数;
a+b=len(S)为偶数;
扫描过程中每遇到一次匹配就a--,b--;每遇到一次替换就a++,b--;
所以扫描过程中a+b始终是偶数;
扫描完成后a=X,b=0, 所以X=a+b也是偶数

2. 经过替换得到的字符串S满足要求
这是因为每个'{'有对应的'}',每个'}'也有对应的'{',且每一对配对的'{'和'}'中间的所有括号都互相配对好了

3.算法达到了所需替换次数的下限
1)当Ai='}'且P为空,说明字符串T=[A1 A2 ... Ai]里面的'}'个数比'{'多,要实现平衡,至少要吧1个'}'替换为'{';
2)当扫描完毕后P中剩下X个元素,设栈底元素为i,则字符串Q=[Ai Ai+1 ... AN]中的'{'比'}'多X个,要实现平衡,至少要把X/2个替换掉;Q中只有Ai='{'可能在1)中替换过了,所以再把X/2个'{'替换为'}'不会造成重复计算;
于是计算出了所需替换次数的一个下限,这个下限正好是上面算法得到的结果,即最小替换次数




Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator