CF 628C --- Bear and String Distance --- 简单贪心

  CF 628C

  题目大意:给定一个长度为n(n < 10^5)的只含小写字母的字符串,以及一个数d,定义字符的dis--dis(ch1, ch2)为两个字符之差,

       两个串的dis为各个位置上字符的dis之和,求和给定的字符串的dis为d的字符串,若含有多个则输出任意一个,不存在输出-1

  解题思路:简单贪心,按顺序往后,对每一个字符,将其变为与它dis最大的字符(a或者z),d再减去相应的dis,

       一直减到d为0,剩余的字母则不变直接输出。若一直到最后一位d仍然大于0,则说明不存在,输出-1.

/* CF 628C --- Bear and String Distance --- 简单贪心 */
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <ctype.h>
using namespace std; char a[]; int main()
{
#ifdef _LOCAL
freopen("D:\\input.txt", "r", stdin);
#endif int n, k;
while (scanf("%d%d", &n, &k) == ){
scanf("%s", a);
for (int i = ; i < n; ++i){
int t = max(a[i] - 'a', 'z' - a[i]);
if (k - t <= ){
if (islower(a[i] - k)){
a[i] -= k;
}
else{
a[i] += k;
}
k = ;
break;
}
else{
k -= t;
if (a[i] < ){
a[i] = 'z';
}
else{
a[i] = 'a';
} }
}//for(i)
if (k > ){
printf("-1\n");
}
else{
printf("%s\n", a);
} } return ;
}

下面是参考别人的代码写出来的,比较容易理解:

/* CF 628C --- Bear and String Distance --- 简单贪心 */
#include <cstdio>
#include <algorithm>
using namespace std; char a[]; int main()
{
int n, k;
while (scanf("%d%d", &n, &k) == ){
scanf("%s", a);
for (int i = ; i < n; ++i){
int dis1 = a[i] - 'a';
int dis2 = 'z' - a[i];
if (dis1 < dis2){
int ddd = min(k, dis2);
k -= ddd;
a[i] += ddd;
}
else{
int ddd = min(k, dis1);
k -= ddd;
a[i] -= ddd;
}
}//for(i)
k ? printf("-1\n") : printf("%s\n", a);
} return ;
}
上一篇:win7 64 安装mysql-python:_mysql.c(42) : fatal error C1083: Cannot open include file: 'config-win.h': No such file or directory


下一篇:Verdigris: Qt without moc