题解：P16173 [ICPC 2015 NAIPC] Zig Zag Nametag

· · 题解

题解：P16173 [ICPC 2015 NAIPC] Zig Zag Nametag

这么简单的题是黄题？

首先，题目要求说要满足要构造一个满足相邻字母的差的和为题目给出的 n 并且要先满足长度最小，再满足字典需最小。

看到这，该不会还有不知道用什么算法的人吧。很明显，我们要用贪心。

首先先用形如 aza…z 和 aza…a 的字符串来满足长度最短，再在字符串后面加上满足剩余的值的字母。例如 77 用上述方法转换成字符串就是 azazx。

接下来就是处理字典序，我们构造出来的字符串不一定是字典序最小的，但一定满足长度最小。我们注意到可以前面的字母减少，把少加的或多加的弄到后面去，例如 azazx 可以把第二位的 z 变为 o，此时与左右的两个a 差值都减少，我们就把最后的 x 变为 b 来解决值的问题。

上代码！

#include<bits/stdc++.h>
using namespace std;
const int N=1e6;
int n,cnt;
char a[N];
int main(){
    cin>>n;
    for(int i=1;i<=n/25+1;i++){
        if(i%2==1) a[++cnt]='a';
        else a[++cnt]='z';
    }
    n%=25;
    if(n>0){
        if(a[cnt]=='z') a[++cnt]=char(97+25-n);
        else a[++cnt]=char(97+n);
    }
    for(int i=1;i<cnt;i++){
        while(a[i]>'a'){
            if(a[cnt-1]-a[cnt]<0&&a[cnt]+2>'z') break;
            if(a[cnt-1]-a[cnt]>0&&a[cnt]-2<'a') break;
            a[i]--;
            if(a[cnt-1]-a[cnt]<0) a[cnt]+=2;
            else a[cnt]-=2;
        }
        if(a[cnt]=='a'||a[cnt]=='z') break;
    }
    for(int i=1;i<=cnt;i++) cout<<a[i];
    return 0;
}

就这么简单。