Lotuses's Blog

CF412A

  • 1026 字

很清晰的思路，就是向左再向右。

绘字符的时间是固定的，想要减少只能减少中间的搬梯子浪费的时间。

向左，为了一次性解决左边的字符，如果不是一直向左，那么中途必定向右，而左边还有未处理的字符，说明还需要返回，这时就浪费了两个小时；向右同理。所以，处理左右两边的字符，要么不处理，要么就直接处理完。

那么，先向左还是先向右呢？

观察发现，先向左，那么中途浪费的时间就是左边节点数的两倍；先向右是右边节点数的两倍。自然是优先选择节点数少的了！

那么，分类讨论，并整理模拟思路，就打出这样的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<bits/stdc++.h>
using namespace std;
char s[10001];

int main()
{
    int n,k;
    cin>>n>>k;
    scanf("%s",s+1);
    if((n-k)>=k)  // 分类讨论
    {             // 模拟
        printf("PRINT %c\n",s[k]);
        for(int i=k-1;i>=1;i--)
            printf("LEFT\nPRINT %c\n",s[i]);
        for(int i=1;i<=k-1;i++)
            printf("RIGHT\n");
        for(int i=k+1;i<=n;i++)
            printf("RIGHT\nPRINT %c\n",s[i]);
    }
    else
    {
        printf("PRINT %c\n",s[k]);
        for(int i=k+1;i<=n;i++)
            printf("RIGHT\nPRINT %c\n",s[i]);
        for(int i=n;i>=k+1;i--)
            printf("LEFT\n");
        for(int i=k-1;i>=1;i--)
            printf("LEFT\nPRINT %c\n",s[i]);
    }
    return 0;
}
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可