首页 > 代码库 > ZOJ 3829 Known Notation(贪心)
ZOJ 3829 Known Notation(贪心)
题目链接
题意 ：给你一个字符串，但是空格丢失，问你需要多少次操作能够让这个字符串可以看成合法的逆波兰式，例如12*3*4不是合法的逆波兰式，但是12*34*可以看成1 2*34*是正确的逆波兰式。
思路 ：当数字的个数比操作符的个数多的时候显然交换所用的操作次数少，只要把操作符往最后换即可。题目中隐含的意思是12你可以看成1和2也可以看成12，做题的时候注意灵活性。
当操作符的个数比数字的个数多的时候，显然插入数字才是正确的做法，只要往前插入即可。一个合法的逆波兰式的操作符的个数最多是数字的个数-1 。
#include <stdio.h>#include <iostream>#include <string.h>using namespace std ;int main(){ int n ; scanf("%d",&n) ; getchar() ; char ch[1100] ; while(n--){ scanf("%s",ch) ; int len = strlen(ch) ; int opcnt = 0 ,numcnt = 0; for(int i = 0 ; i < len ; i++) { if(ch[i] == ‘*‘) { opcnt++ ; } } if(opcnt == 0) { printf("0\n") ; continue ; } int cnt = 0 ;//*前边的数字的数量 int ans = 0 ; numcnt = len - opcnt ; for(int i = 0 ; i < len ; i++) { if(ch[i] == ‘*‘) { if(cnt > 1) cnt-- ;//只要前边有数字，*就要一直消耗掉，消耗不掉的看成一个数 else { if(numcnt > opcnt)//数字多，*往后换 { for(int j = len-1 ; j >= 0 ; j--) { if(ch[j] != ‘*‘) { swap(ch[i],ch[j]) ; cnt ++ ; ans ++ ; break ; } } } else { ans ++ ; numcnt ++ ;//数不够，插入数字 if(cnt == 0)//字符串第一个是*的时候 { i -- ; cnt = 1 ; } } } } else cnt ++ ; } printf("%d\n",ans) ; } return 0 ;}
ZOJ 3829 Known Notation(贪心)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。