【CF 1011A】 Stages
A. Stages
Natasha is going to fly to Mars. She needs to build a rocket, which consists of several stages in some order. Each of the stages is defined by a lowercase Latin letter. This way, the rocket can be described by the string — concatenation of letters, which correspond to the stages.
There are nn stages available. The rocket must contain exactly kk of them. Stages in the rocket should be ordered by their weight. So, after the stage with some letter can go only stage with a letter, which is at least two positions after in the alphabet (skipping one letter in between, or even more). For example, after letter 'c' can't go letters 'a', 'b', 'c' and 'd', but can go letters 'e', 'f', ..., 'z'.
For the rocket to fly as far as possible, its weight should be minimal. The weight of the rocket is equal to the sum of the weights of its stages. The weight of the stage is the number of its letter in the alphabet. For example, the stage 'a 'weighs one ton,' b 'weighs two tons, and' z' — 2626 tons.
Build the rocket with the minimal weight or determine, that it is impossible to build a rocket at all. Each stage can be used at most once.
Input
The first line of input contains two integers — nn and kk (1≤k≤n≤501≤k≤n≤50) – the number of available stages and the number of stages to use in the rocket.
The second line contains string ss, which consists of exactly nn lowercase Latin letters. Each letter defines a new stage, which can be used to build the rocket. Each stage can be used at most once.
Output
Print a single integer — the minimal total weight of the rocket or -1, if it is impossible to build the rocket at all.
Examples
input
5 3
xyabd
output
29 input
7 4
problem
output
34 input
2 2
ab
output
-1 input
12 1
abaabbaaabbb
output
1
题目大意是给你一个由26个字母组成的字符串组成一个火箭，每个字符的重量为它本身的序号（如a=1,b=2...z=26）。
组成火箭每个字符的重量必须是递增的，且重量相同或相邻的字母不能放在一起（c的后面不能放a,b,和d）。
给出字母个数 n 和火箭的长度 k，求火箭的最小重量。
对字符串进行处理，获得的值存起来进行排序，再通过条件1和2进行判断即可。
考虑过用set做，不过迭代器用的不习惯QAQ
文章最后有爬下来的后台数据，可以自己进行测试。
代码：
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdio>
#include<cmath>
#include<set>
using namespace std;
#define inf 0x3f3f3f3f
#define ll long long
int main()
{
int n,m,i,j,k,x,t,a[55],sum=0;
string s;
cin>>n>>m;
getchar();
cin>>s;
for(i=0; i<n; i++)
a[i]=s[i]-'a'+1;
sort(a,a+n);
j=1;
for(i=1; i<n; i++)
if(a[i]!=a[i-1])
j++;
/*cout<<j<<endl;
for(i=0;i<n;i++)
cout<<a[i]<<" ";*/
if(j<m)
{
cout<<"-1"<<endl;
return 0;
}
sum+=a[0];
m--;
t=a[0];
for(i=1; i<n; i++)
{
if(m==0)
break;
if(a[i]-t>1)
{
t=a[i];
sum+=a[i];
m--;
}
}
if(m==0)
cout<<sum<<endl;
else
cout<<"-1"<<endl;
return 0;
} 测试数据：
5 3
xyabd29
29
ok 1 number(s): "29"7 4
problem34
34
ok 1 number(s): "34"2 2
ab-1
-1
ok 1 number(s): "-1"12 1
abaabbaaabbb1
1
ok 1 number(s): "1"50 13
qwertyuiopasdfghjklzxcvbnmaaaaaaaaaaaaaaaaaaaaaaaa169
169
ok 1 number(s): "169"50 14
qwertyuiopasdfghjklzxcvbnmaaaaaaaaaaaaaaaaaaaaaaaa-1
-1
ok 1 number(s): "-1"1 1
a1
1
ok 1 number(s): "1"50 1
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa1
1
ok 1 number(s): "1"50 2
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa-1
-1
ok 1 number(s): "-1"13 13
uwgmkyqeiaocs169
169
ok 1 number(s): "169"13 13
hzdxpbfvrltnj182
182
ok 1 number(s): "182"1 1
n14
14
ok 1 number(s): "14"10 8
smzeblyjqw113
113
ok 1 number(s): "113"20 20
tzmvhskkyugkuuxpvtbh-1
-1
ok 1 number(s): "-1"30 15
wjzolzzkfulwgioksfxmcxmnnjtoav-1
-1
ok 1 number(s): "-1"40 30
xumfrflllrrgswehqtsskefixhcxjrxbjmrpsshv-1
-1
ok 1 number(s): "-1"50 31
ahbyyoxltryqdmvenemaqnbakglgqolxnaifnqtoclnnqiabpz-1
-1
ok 1 number(s): "-1"10 7
iuiukrxcml99
99
ok 1 number(s): "99"38 2
vjzarfykmrsrvwbwfwldsulhxtykmjbnwmdufa5
5
ok 1 number(s): "5"12 6
fwseyrarkwcd61
61
ok 1 number(s): "61"2 2
ac4
4
ok 1 number(s): "4"1 1
c3
3
ok 1 number(s): "3"2 2
ad5
5
ok 1 number(s): "5"2 1
ac1
1
ok 1 number(s): "1"4 3
adjz15
15
ok 1 number(s): "15"3 3
aoz42
42
ok 1 number(s): "42"3 1
zzz26
26
ok 1 number(s): "26"2 1
xz24
24
ok 1 number(s): "24"5 1
aaddd1
1
ok 1 number(s): "1"
