大家好,又见面了,我是全栈君。
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3829
现场做这道题的时候,感觉是思维题。自己智商不够。不敢搞,想着队友智商好,他们搞吧。可是没出来这题……
以后不论什么时候,都自信点….该想的还是好好自己想,这类题感觉就是先去找性质,然后一点点找规律,假设必要的话。自己提出一点猜想。然后假设自己举不出来反例,就临时觉得是正确的
下午搞了一下午。发现还是悲剧,晚上參考了两个题解
http://blog.csdn.net/keshuai19940722/article/details/40039975
事实上至少能够总结出来一下规律:
1、必须num(*)<num(数字)
2、前面全是数字的后面全是*是合法的。就是说,假设须要交换的话,能够把*全换到最后,就是把*和最后的数字交换位置,反正每次耗费都是1
3、由于交换一次耗费为1,插入一次耗费也是1,所以假设不满足规律1,能够先插入,又由于规律2,所以把数字在一開始就所有插入到最前面,用栈模拟后缀表达式的验证过程,假设缺数字。就把最后的数字和当前的*交换位置,根据是规律2.不会缺星号的。由于连续的数字能够当做同一个数字
以上三条足够解决这个问题
#include <cstdio> #include <cstring> #include <algorithm> #include <iostream> using namespace std; const int MAXN = 1000+50; #define CL(a,b) memset(a,b,sizeof(a)) #define ll long long #define ull unsigned long long #define IN(s) freopen(s,"r",stdin) char str[MAXN],sta[MAXN*10]; int pos[MAXN*10]; int len,numa,numb,tp,postp; void init() { tp=postp=0; numa=numb=0;// scanf("%s",str); len=strlen(str); } ll solve() { for(int i=0;i<len;i++) { if(str[i] == '*') numa++; else { numb++; pos[postp++]=i; } } if(numa == 0)return 0;//****特判 ll ans=0; tp=max(numa+1-numb,0);//假设数字多。总是能够组合出来的 //在开头补上数字 ans=(ll)tp; for(int i=0;i<len;i++) { if(str[i] == '*'){ if(tp>=2)tp--; else{ str[pos[postp-1]]='*'; postp--; tp++; ans++;//交换没有强调相邻 } } else tp++; } if(ans==0 && str[len-1]!='*')ans++;// return ans; } int main() { //IN("K.txt"); int ncase; scanf("%d",&ncase); while(ncase--) { init(); printf("%lld\n",solve()); } return 0; }
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/116268.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...