2019 计蒜之道复赛 - D. “星云系统”

题目描述

VIPKID 是在线少儿英语教育平台，网络稳定是在线教育课程质量的红线，VIPKID 为此推出了全球最稳定的教育网络系统 —— “星云系统”。星云系统目前建立了覆盖全球 3535 个国家的 55 条核心跨海专线，在 1616 个国家的 5555 个城市建立了中心传输节点，具备一分钟内自由切换路由的能力，确保了全球跨洋课堂的高清音、视频通信，为流畅的课堂体验打下坚实基础。

全世界的中心传输节点和各地的网络节点组成的这个“星云系统”，何其复杂。我们现在只考虑一条支线上的网络节点，每一个网络节点比作一个字符的话，这条支线就是一个字符串。

现在给定你一个字符串 ss 以及一个整数 kk，请求出 ss 的字典序最小的长度为 kk 的子序列。

输入格式

1	第一行一个由小写英文字母构成的字符串 ss，第二行一个正整数 kk。

输出格式

1	一行一个字符串 ans，表示答案。

数据规模

1	0<k≤∣s∣≤5000000

样例输入

1 2	helloworld 5

样例输出

ellld

求解过程

解法有点贪心的思想，每次选出“可选区间”内的最小字符，每次在这个区间内找出最下的字符，选k次就好了。

假设字符串为”helloworld”, k = 5，为了保证选取的子序列长度为5，那么第一次可取的区间[0,5]（超过5的话即使后面的全选也凑不齐k个字符了）

每取完第i个字符后，剩下的字符应该至少在当前选中位置pos的下一位开始。

容易得到“可选区间”上边界为pos + 1, 下边界为∣s∣ - (k - (i + 1))。（|s|表示字符串长度）

事实上即使这样还是超时，学弟考虑了测试数据的一种极端情况：全由‘a’组成的长字符串，于是就有了第16行的优化。

AC代码

#include<iostream>
#include<cstring>
#include<cstdio> 
using namespace std;
const int maxn = 5e6 + 10;
char out[maxn], str[maxn];
int main() {
  int k;
  scanf("%s", str);
  scanf("%d", &k);
  int len = strlen(str);
  int l = 0, r = len - k, pos = 0;
  for (int i = 0; i < k; i++) {
    char min_ch = 'z' + 1;
    for (int j = l; j <= r; j++) {
      if (str[j] == 'a') {
        min_ch = 'a';
        pos = j;
        break;
      } else {
        if (str[j] < min_ch) {
          min_ch = str[j];
          pos = j;
        }
      }
    }
    l = pos + 1, r = len - (k - (i + 1));
    out[i] = min_ch;
  }
  printf("%s", out);
  return 0;
}