第九届河南理工大学算法程序设计大赛-E.Mo的游戏

E. Mo的游戏

单测试点时限: 1.0 秒

内存限制: 512 MB

Mo翻书看到一种新的连连看游戏：对于一个字符串来说，只有当两个字符相同时候才可以进行相连，得分为字符串的长度减去两个相连字符的距离（如果整个字符串中某一种字符个数为1，那么不能相连故得分为0）。Mo现在在玩这个游戏，但是Mo不知道该选择哪一种字符进行相连，所以请你列出每种字符相连可以获得的最大分数，以此来让Mo进行参考。

输入

一个字符串s （0<strlen(s)<106， s中只包含大小写字符）。

输出

针对s中出现过的字符，每行输出一个整数表示用当前字符进行相连可以获得的最大分数, 按照a−z，A−Z的顺序。具体格式参见样例。

样例

input

Aabcaabcb

output

a:8
b:7
c:5
A:0

思路：通过读题，不难得出，字符的得分 = 字符串的长度 — 同样的字符之间的距离；

只要求出每种同样字符之间最小的距离就行了：

#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;
struct su{
	char st;
	int v;
};
int main(){
	string s;
	cin>>s;
	map<char,int> last;  //上一个同样字符的位置 
	map<char,int> m;     //统计字符个数 
	map<char,int> ans;   //结果 
	vector<su> v;
	int n=s.length();
	
	for(int i=0;i<n;i++){
		m[s[i]]++;           //计数 
		if(m[s[i]]<2){
			last[s[i]]=i;    //每种符号的第一次出现 
		}
		else if(m[s[i]]==2){    //第二次出现，这时候才可以"对消" 
			ans[s[i]]=i-last[s[i]];  //ans[]：记录第一个可能为答案的数值 
			last[s[i]]=i;        //更新位置 
		}
		else {
			ans[s[i]]=min(ans[s[i]],i-last[s[i]]);  //ans[]：记录两个相邻同样字符距离最小值 
			last[s[i]]=i;    
		}
	}
	
	map<char,int>::iterator it=m.begin();
	su r;
	for(;it!=m.end();it++){
		r.st=it->first;
		if(ans[r.st])
		r.v=n-ans[r.st];
		else
		r.v=0;
		v.push_back(r); 
	}
	for(int i=0;i<v.size();i++){    //不想排序了，直接输出QAQ 
		if(v[i].st>='a'&&v[i].st<='z')
		cout<<v[i].st<<":"<<v[i].v<<endl;
	}
	for(int i=0;i<v.size();i++){
		if(v[i].st>='A'&&v[i].st<='Z')
		cout<<v[i].st<<":"<<v[i].v<<endl;
	}
	

	return 0;
}