首页 > 代码库 > ZOJ 3829 模拟贪心
ZOJ 3829 模拟贪心
2014牡丹江现场赛水题
给出波兰式,判断其是否合法,如果不合法有两种操作:
1:任意位置加一个数字或者操作符
2:任意两个位置的元素对调
贪心模拟即可
先判断数字数是否大于操作符数,若不大于 ans+=sum2-sum1+1;新加入的数字全部放到左端。
然后从左到右遍历一遍,存储到当前位置为止,数字数和sum1,和操作数和sum2
若sum2>=1sum1,优先与队尾的数字对调,若没有则sum1++,表示在最左端加一个数字
#include "stdio.h" #include "string.h" int main() { int n,sum1,sum2,i,len,ans,j,ok; char str[1010]; scanf("%d",&n); while (n--) { scanf("%s",str); sum1=sum2=0; len=strlen(str); for (i=0;str[i];i++) if (str[i]=='*') sum2++; else sum1++; if (sum2==0) { printf("0\n"); continue; } if (sum1==0) { printf("%d\n",sum2+1); continue; } ans=0; if (sum1<=sum2) { ans+=sum2-sum1+1; sum2=0; sum1=ans; } else sum1=sum2=0; for (i=0;str[i];i++) { if (str[i]<='9' && str[i]>='1') {sum1++; continue;} if (str[i]=='*') sum2++; if (sum1>sum2) continue; else { ok=0; for (j=len-1;j>i;j--) if(str[j]<='9' && str[j]>='1') { ans++; sum1++; sum2--; str[j]='*'; ok=1; break; } if (ok==0) { if (i==0) { ans+=2; sum1+=2; } else { ans++; sum1++; } } } } if (str[len-1]!='*') ans++; printf("%d\n",ans); } return 0; }
ZOJ 3829 模拟贪心
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。