首页 > 代码库 > SGU 170.Particles
SGU 170.Particles
Solution:
这其实是道很简单的题。
只要从一端开始,以‘+’或‘-’,任意一种开始找,找到与目标串最近的相同字符的距离就是需要交换的次数。
+++——— 对齐第一个‘-’ —+++——
------------>
———+++ ———+++
以‘-’为例,不断向一端交换的话,最后交换的其实只要当前的‘-’和一个‘+’的位置,其他‘-’的相对位置不变。
因此只要从左到右匹配第i个‘-’,计算出它们的距离差,累加即可。
code:
#include <iostream>#include <string>#define abs(x) (max(x,-(x)))using namespace std;const int INF = 5555;int len, a[INF], b[INF], n1, n2, ans;string st;int main() { cin >> st; len = st.size(); for (int i = 0; i < len; i++) if (st[i] == ‘-‘) a[++n1] = i; cin >> st; for (int i = 0, t = 0; i < len; i++) if (st[i] == ‘-‘) b[++n2] = i; if (n1 != n2) { cout << -1; return 0; } for (int i = 1; i <= n1; i++) ans += abs (a[i] - b[i]); cout << ans;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。