尺取练习

尺取练习

题目链接

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 n stages available. The rocket must contain exactly k 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’ — 26 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.

The first line of input contains two integers — n and k (1≤k≤n≤50) – the number of available stages and the number of stages to use in the rocket.

The second line contains string s, which consists of exactly n 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.

Print a single integer — the minimal total weight of the rocket or -1, if it is impossible to build the rocket at all.

In the first example, the following rockets satisfy the condition:

“adx” (weight is 1+4+24=29);
“ady” (weight is 1+4+25=30);
“bdx” (weight is 2+4+24=30);
“bdy” (weight is 2+4+25=31).
Rocket “adx” has the minimal weight, so the answer is 29.

In the second example, target rocket is “belo”. Its weight is 2+5+12+15=34.

In the third example, n=k=2, so the rocket must have both stages: ‘a’ and ‘b’. This rocket doesn’t satisfy the condition, because these letters are adjacent in the alphabet. Answer is -1.

题意：就是给一串小写字符串含有n个字符，然后就是要k个字符，要求时k个字符和最小，并且按照字典序取得这k个字符，但是k个小写字母必须是相邻两个必须隔着至少一个小写字母。说不太清楚，看看样例就很好理解了

思路：就是取k个的话，k>=1,要和最小，那么从小到大排序后的第一个肯定是要的！然后的话后面要尽可能的取小的，但又有条件约束，所以就判断当前这个位置与前一个已经被取到的的差值，如果这个不符，那么下一个肯定是符合的！

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;int a[55];int main(){int n,k;cin>>n>>k;char c;for(int i=0;i<n;i++){cin>>c;a[i] = c - 'a'+1;//cout<<a[i]<<" ";}sort(a,a+n);int sum = a[0];//因为k是大于等于1，所以第一个肯定是符合的 int flag = 1;int rec = 0;for(int i=1;i<n;i++){//在找k-1个； if(flag >= k) break;rec += a[i]-a[i-1];if(rec > 1){sum += a[i];rec = 0;flag++;}}if(flag < k) cout<<-1<<endl;else  cout<<sum<<endl;return 0;
}