首页 > 代码库 > 2014牡丹江——Known Notation
2014牡丹江——Known Notation
题目链接
- 题意:
输入一个长度不超过1000的字符串,包含数字(1-9)和星号(*)。字符串中的空格已经丢失,所以连起来的数字串能够看成很多分开的数。也能够看成连续的数,即能够随意加入空格。如今有两种操作:1)在任何位置加入随意类型的字符(数字或者星号) 2)交换字符串中的随意两个字符
求:最少操作多少次,使得得到的串是一个合法的逆波兰式 - 分析:
对于n个星号,n+1个数字的字符串,假设将星号都移动到串的末尾。那么一定是合法的
对于操作1,假设须要插入数字,那么插入到字符串的最前边是最优的
对于操作2,仅仅可能将星号和数字交换。而且将星号移到了字符串的后边
那么,先对串进行操作1,使得数字个数不小于星号的个数加一;然后从左到右扫描字符串,假设当前星号前边的数字和星号不满足相应关系(同上)。须要将当前星号与最后一个数字交换;最后,假设字符串最后不是星号。答案加一 - 注意:
假设最后得到的串最后不是星号。那么必定答案加一
假设输入没有星号。那么答案是0
const int maxn = 1100; char s[maxn]; int n; vector<int> v; int main() { int T; RI(T); while (T--) { v.clear(); RS(s); n = strlen(s); int num = 0, sig = 0; REP(i, n) { if (s[i] == ‘*‘) sig++; else { v.push_back(i); num++; } } int ans = 0; int preadd = 0; if (!sig) { ans = 0; } else { if (num < sig + 1) { preadd = sig + 1 - num; ans += preadd; } int sig_num = 0; for (int i = 0; i < n; i++) { if (s[i] == ‘*‘) { sig_num++; if (preadd < sig_num + 1) { int sz = v.size(); int id = v[sz - 1]; v.pop_back(); swap(s[i], s[id]); sig_num--; preadd++; ans++; } } else preadd++; } if (s[n - 1] != ‘*‘) ans++; } printf("%d\n", ans); } return 0; }
2014牡丹江——Known Notation
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。