pipioj 1034: 字典序最小的子序列（贪心）

 1 #define bug(x) cout<<#x<<" is "<<x<<endl
 2 #define IO std::ios::sync_with_stdio(0)
 3 #include <bits/stdc++.h>
 4 using namespace  std;
 5 typedef long long ll;
 6 #define mk make_pair
 7 #define pb push_back
 8 const int inf=2147483647;
 9 const int N=1e5+10;
10 int k;
11 int a[N][26];
12 int id[200];
13 char s[N];
14 int main(){
15     while(~scanf("%d",&k)){
16         scanf("%s",s+1);
17         int n=strlen(s+1);
18         for(int i=0;i<26;i++){
19             a[n+1][i]=n+1;
20         }
21         for(int i=n;i>=0;i--){
22             for(int j=0;j<26;j++){
23                 if(s[i]==j+'a')a[i][j]=i;
24                 else a[i][j]=a[i+1][j];
25             }
26         }
27         int i=0,cnt=1;
28         for(;i<=n&&cnt<=k;){
29             for(int j=0;j<26;j++){
30                 int x=a[i][j];
31                 if(x<=n-k+cnt){
32                     cnt++;
33                     printf("%c",j+'a');
34                     i=x+1;
35                     break;
36                 }
37             }
38         }
39         printf("
");
40     }
41 }