题目链接:http://codeforces.com/contest/1107/problem/C
题意是给了n个只含有小写字母的字符串,每个字符都有一个权值,又输入一个k,表示相同字符最多连续k个,题目要求输出选哪些字符可以使得权值最大,比如k等于3的时候,aaaa就只能选其中的三个(任意三个,不是连着的三个)。
当时因为没有读懂题意,然后按着错误的题意写了份code,测样例的时候才发现不对...正确的写法就是找到连续的字符串,然后按权值从大到小选k个就好了。看代码吧,不难理解。
AC代码:
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll pre[200005];
int n,m;
int T;
bool cmp(ll a, ll b){
return a > b;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++){
scanf("%lld",&pre[i]);
}
string str;
cin>>str;
str += '+'; // 一个预处理
ll ans = 0;
n ++;
int k = 0;
vector<ll> v;
for(int i=1;i<n;i++){
if(str[i] == str[i-1]){
v.push_back(pre[i-1]);
}
else{
v.push_back(pre[i-1]);
sort(v.begin(), v.end(), cmp);
int xx = 0;
for(int i=0;i<m && i <v.size();i++){
ans += v[i];
xx ++;
}
v.clear();
}
}
cout<<ans<<endl;
return 0;
}