Codeforces 724D - Dense Subsequence

#贪心
Published on 2016-10-09

题目地址

描述

有一个长度为 n(n≤100000)n(n\le 100000) 的字符串，你需要选出若干个位置，使得每个长度为 m(1≤m≤n)m(1\le m\le n) 的字串至少有一个位置被选择，将选择的位置上的字符组成一个新的字符串，你需要输出字典序最小的那个。

分析

首先，我们将 “使得每个长度为 mm 至少有一个位置被选择” 这个条件转换，不难发现，这个条件可以转化为：将选择的位置（加上一个 −1-1）从小到大排序，相邻两个位置之间的间隔不超过 mm。

接着我们就是要做出一个字典序最小的串，运用贪心思想，首先考虑字符 a，如果将所有的 a 全部选上还不能满足条件，那么我们一定要选所有的 a；反之，如果将所有的 a 全部选上可以满足条件，那么我们就要选择最少数量的 a 使得能够满足条件，而且我们不再选比 a 大的字符。

也就是，我们顺序地考虑 26 种字符，考虑全选某一种字符是否可以成立，如果不成立，必须全选（因为必然要选比当前字符大的字符，如果不全选，字典序一定比全选大）；如果成立，我们必须选择最少数量的当前字符，这个可以使用贪心算法，只在必须要选的时候选择。

贪心比较精妙，详细见代码。

代码

//  Created by Sengxian on 2016/10/09.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  Codeforces 724D 贪心
#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 100000 + 3, SIGMA_SIZE = 26;
int n, m, cnt[SIGMA_SIZE];
char str[MAX_N];

int work(char ch) {
    int cnt = 0, last = -1, lastch = -1;
    for (int i = 0; i < n; ++i) {
        if (str[i] < ch) last = i;
        else if (str[i] == ch) lastch = i;
        if (i - last == m) {
            if (lastch <= last) return -1;
            cnt++;
            last = lastch;
        }
    }
    return cnt;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
#endif
    scanf("%d%s", &m, str);
    n = strlen(str);
    for (int i = 0; i < n; ++i) cnt[str[i] - 'a']++;
    static char ans[MAX_N];
    int iter = 0;
    for (int i = 0; i < SIGMA_SIZE; ++i) {
        int k = work('a' + i);
        if (k != -1) {
            for (int j = 0; j < k; ++j)
                ans[iter++] = 'a' + i;
            break;
        } else for (int j = 0; j < cnt[i]; ++j)
                ans[iter++] = 'a' + i;
    }
    ans[iter] = 0;
    printf("%s\n", ans);
    return 0;
}
Codeforces 724E - Goods transportation