首页 > 代码库 > zoj 3829 Known Notation
zoj 3829 Known Notation
题目链接: zoj 3829 Known Notation 作者:jostree 转载请说明出处
使用贪心+模拟。由于没有数字之间没有空格，因此该题有如下性质：
1.如果该字符串全部为数字，则无需操作，直接输出0。
2.连续的n个数字后面接连续的m个*，当n>m时，一定是有效的答案。从而最终的目的就是把最后的数字尽量向前移动，把最前面非法的*尽量向后移动，因此insert操作添加数字时，只需添加在最前面即可。
3.*的个数一定要小于数字的个数，因为每个*号需要消耗掉一个数字，并且首个*消耗掉2个数字。因此如果发现数字的个数比*的个数少k个，那么需要直接在字符串首添加k+1个数字。
4.如果字符串非全数字，那么结尾的数字一定要被替换成*，否则串无效。因此遇到第一个*时，直接与结尾的数字交换。
5.遍历整个串，当发现*的个数大于等于数字的个数时，直接把该位置的*与最后的数字进行替换。
代码如下：
1 #include <cstdio> 2 #include <cstdlib> 3 #include <iostream> 4 #include <cstring> 5 using namespace std; 6 char str[1010]; 7 void solve() 8 { 9 int len = strlen(str);10 int nnum = 0, nstar = 0;11 int pnum = len-1;12 int res = 0;13 int leftnum = 0;14 for( int i = 0 ; i < len ; i++ )15 {16 if( str[i] == ‘*‘ ) nstar++;17 else nnum++;18 }19 if( nnum == len )20 {21 printf("0\n");22 return;23 }24 if( nnum - nstar <= 0)25 {26 leftnum = nstar -nnum + 1;27 res += leftnum;28 }29 for( int i = 0 ; i < len ; i++ )30 {31 while( i < pnum && str[pnum] == ‘*‘) pnum--;32 if( str[i] == ‘*‘ )33 {34 leftnum--; 35 if( pnum == len-1 && str[pnum] != ‘*‘ )36 {37 str[i] = str[pnum];38 str[pnum] = ‘*‘;39 leftnum += 2;40 res++;41 pnum--;42 }43 else if( leftnum <= 0 )44 {45 str[i] = str[pnum];46 str[pnum] = ‘*‘;47 res++;48 leftnum += 2;49 }50 }51 else leftnum++;52 }53 printf ( "%d\n", res );54 }55 int main(int argc, char *argv[])56 {57 int T;58 scanf("%d", &T);59 while( T-- )60 { 61 scanf ( "%s", str );62 solve();63 }64 }
另附测试用例：
1***1**11*1*1*1*1*1*11**1111*1111*1111**1*111***1111****111111**1**1*1**1**1111***1111**1*111**11***111*****1*1**111**11**331120111223311134321122
zoj 3829 Known Notation
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。