51nod 1255 贪心/构造

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1255

1255 字典序最小的子序列

题目来源：天津大学OJ

基准时间限制：1 秒空间限制：131072 KB 分值: 40 难度：4级算法题

关注

给出一个由a-z组成的字符串S，求他的一个子序列，满足如下条件：

1、包含字符串中所有出现过的字符各1个。

2、是所有满足条件1的串中，字典序最小的。

例如：babbdcc，出现过的字符为：abcd，而包含abcd的所有子序列中，字典序最小的为abdc。

Input

输入1行字符串S，所有字符均为小写，字符串的长度为L。(1 <= L <= 100000)。

Output

输出包含S中所有出现过的字符，每个字符各1个，并且字典序最小的S的子序列。

Input示例

babbdcc

Output示例

abdc
  
一开始只考虑了待替换字符后面相邻的那一个字符没想到还有可能出现后面数个在后面都可以被更换使得字典序更小的情况，改了以后还是WA竟然是因为前缀和数组zz的写错了cao。。。
假设字符x已经出现过了，现在考虑将x删掉查到后面会不会使得结果更优，那么x后面肯定要出现一个小于x的字符且这二者间的字符再后面都要能替换，否则的话并不能使答案优化。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 char s[100005];
 4 deque<char>q;
 5 bool vis[26];
 6 int num[26];
 7 int main()
 8 {
 9     scanf("%s",s+1);
10     int len=strlen(s+1),n,m,i,j,k;
11     for(i=1;i<=len;++i) num[s[i]-'a']++;
12     for(i=1;i<=len;++i)
13     {
14         if(!vis[s[i]-'a']){
15             vis[s[i]-'a']=1;
16             q.push_back(s[i]);
17         }
18         else{
19             for(j=0;j<q.size();++j)
20             {
21                 if(q[j]==s[i]){int j1=-1;
22                 {
23                             for(k=j+1;k<q.size();++k){
24                                 if(q[k]<q[j]){j1=k;break;}
25                             }
26                     if(j1!=-1){
27                         bool ok=1;
28                         for(k=j+1;k<j1;++k)
29                         {
30                             if(num[q[k]-'a']<=0){ok=0;break;}
31                         }
32                         if(ok){
33                             q.erase(q.begin()+j);
34                             q.push_back(s[i]);
35                         }
36                     }
37                     }
38                     break;
39                 }
40             }
41         }
42         num[s[i]-'a']--;
43     }
44     for(int i=0;i<q.size();++i)cout<<q[i];puts("");
45     return 0;
46 }

还有一种做法是用栈。

如果当前元素已经在栈中，则不用操作，否则判断栈顶元素大于当前元素的在后面是否还会出现，如果会的话pop掉，直到栈空或不满足条件或栈顶元素小的情况停止pop，把si入栈。二者时间差不大多。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 char s[100005];
 4 stack<char>q;
 5 bool vis[26];
 6 int num[26];
 7 void out()
 8 {
 9     if(q.empty()) return;
10     char c=q.top();q.pop();
11     out();
12     cout<<c;
13 }
14 int main()
15 {
16     scanf("%s",s+1);
17     int len=strlen(s+1),n,m,i,j,k;
18     for(i=1;i<=len;++i) num[s[i]-'a']++;
19     for(i=1;i<=len;num[s[i++]-'a']--)
20     {
21             if(vis[s[i]-'a']) continue;
22             while(!q.empty()&&q.top()>s[i]&&num[q.top()-'a']>0) {vis[q.top()-'a']=0;q.pop();}
23             q.push(s[i]);
24             vis[s[i]-'a']=1;
25     }
26     out();puts("");
27     return 0;
28 }