題目鏈接

題意 ：給你一個字符串，但是空格丟失，問你需要多少次操作能夠讓這個字符串可以看成合法的逆波蘭式，例如12*3*4不是合法的逆波蘭式，但是12*34*可以看成1 2*34*是正確的逆波蘭式。

思路 ：當數(shù)字的個數(shù)比操作符的個數(shù)多的時候顯然交換所用的操作次數(shù)少，只要把操作符往最后換即可。題目中隱含的意思是12你可以看成1和2也可以看成12，做題的時候注意靈活性。

當操作符的個數(shù)比數(shù)字的個數(shù)多的時候，顯然插入數(shù)字才是正確的做法，只要往前插入即可。一個合法的逆波蘭式的操作符的個數(shù)最多是數(shù)字的個數(shù)-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 ;//*前邊的數(shù)字的數(shù)量int ans = 0 ;numcnt = len - opcnt ;for(int i = 0 ; i < len ; i++){if(ch[i] == '*'){if(cnt > 1) cnt-- ;//只要前邊有數(shù)字，*就要一直消耗掉，消耗不掉的看成一個數(shù)else{if(numcnt > opcnt)//數(shù)字多，*往后換 {for(int j = len-1 ; j >= 0 ; j--){if(ch[j] != '*'){swap(ch[i],ch[j]) ;cnt ++ ;ans ++ ;break ;}}}else{ans ++ ;numcnt ++ ;//數(shù)不夠，插入數(shù)字if(cnt == 0)//字符串第一個是*的時候 {i -- ;cnt = 1 ;}}}}else cnt ++ ;}printf("%d\n",ans) ;}return 0 ; } View Code

?

轉載于:https://www.cnblogs.com/luyingfeng/p/4039797.html

總結

以上是生活随笔為你收集整理的ZOJ 3829 Known Notation(贪心)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。