第一行输入一个整数,代表接下来有组测试数据。
对于每一组测试数据,第一行输入两个数代表字符串的长度和可以删除的字符数量。
接下来输入长度为字符串。
对于每一组数据,输出一个答案
2 5 2 abcab 10 4 lkqijxsnny
aab ijsnny
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.Stack; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int T = Integer.parseInt(br.readLine().trim()); while(T -- > 0){ String[] params = br.readLine().split(" "); int n = Integer.parseInt(params[0]); int m = Integer.parseInt(params[1]); String str = br.readLine().trim(); System.out.println(delete(str.toCharArray(), n, m)); } } private static String delete(char[] str, int n, int m) { Stack<Character> stack = new Stack<>(); int removeCharNums = 0; for(int i = 0; i < n; i++){ char c = str[i]; while(!stack.isEmpty() && c < stack.peek() && removeCharNums < m){ stack.pop(); removeCharNums += 1; } stack.push(c); } StringBuilder sb = new StringBuilder(); while(!stack.isEmpty()) sb.append(stack.pop()); return sb.reverse().toString().substring(0, n - m); } }scala版
import scala.io.StdIn import scala.collection.mutable._ object Main { def main(args: Array[String]): Unit = { var T = StdIn.readInt while(T > 0){ val params = StdIn.readLine.trim.split(" ") val n = params(0).toInt val m = params(1).toInt var str = StdIn.readLine.trim str = deleteChar(n, m, str) println(str) T -= 1 } } def deleteChar(n: Int, m: Int, str: String): String = { val stack = Stack[Char]() var removeCharNum = 0 val chars = str.toArray for(i <- chars.indices){ val c = chars(i) while(!stack.isEmpty && stack.top > c && removeCharNum < m){ stack.pop removeCharNum += 1 } stack.push(c) } val buffer = ArrayBuffer[Char]() while(!stack.isEmpty) buffer.append(stack.pop) buffer.reverse.mkString.substring(0, n - m) } }
可知要想使一个字符串的字典序变小, 优先消除的应该是最左边的逆序对, 之后删除的应该是最右边的元素
可以用一个栈找到找到删掉逆序对后字典序最小的子序列, 不足m的依次出栈即可
#include <iostream> using namespace std; void slove() { int n, m; cin >> n >> m; string s; cin >> s; string res; int cnt = 0; for(int i = 0; i < n; ++ i) { while(!res.empty() && res.back() > s[i] && cnt < m) { res.pop_back(); cnt ++ ; } res.push_back(s[i]); } while(cnt < m) { res.pop_back(); cnt ++; } cout << res << endl; } signed main() { int T; cin >> T; while(T--) slove(); }
#include <iostream> #include <string> using namespace std; int main(){ int T, n, m; string str; cin>>T; while(T){ T--; cin >> n >> m; cin >> str; //寻找逆序,若当前字符大于下一个字符,则将当前字符循环删除, //直到当前字符小于下一个字符 string ss = ""; int p = 0; while(p<n){ //当前字符小于下一个字符,或者删除字符数量已经到m if(ss.empty() || m<=0 || ss.back()<=str[p]){ ss += str[p]; p++; } //当前字符大于下一个字符,需将当前字符删除 else{ while(m && !ss.empty() && ss.back()>str[p]){ ss.pop_back(); m--; } } } //最后全升序,没删够数,从后向前删除 while(m){ ss.pop_back(); m--; } cout << ss <<endl; } return 0; }
import java.util.*; public class Main{ public static void main(String[] args){ Scanner cin = new Scanner(System.in); int T = cin.nextInt(); while(T-- > 0){ int n = cin.nextInt(); int m = cin.nextInt(); cin.nextLine(); String str = cin.nextLine(); Deque stack = new LinkedList(); for(int i = 0; i < n; i++){ while(m > 0 && !stack.isEmpty() && stack.peek() > str.charAt(i)){ stack.pop(); m--; } stack.push(str.charAt(i)); } StringBuffer sb = new StringBuffer(); while(!stack.isEmpty()){ sb.insert(0, stack.pop()); } System.out.println(sb.toString().substring(0, sb.length() - m)); } } }
最后 substring(0, sb.length() - m)
的作用是,循环结束后可能 m
还是大于0的,说明后面字符已经没有逆序,则只能从尾巴截掉剩余的m个字符
#include <iostream> using namespace std; int main() { int T; cin >> T; while (T--) { int n, m; cin >> n >> m; string s; cin >> s; string ans; for (char c : s) { while (!ans.empty() && an***ack() > c && m) { ans.pop_back(); --m; } ans.push_back(c); } while (m--) { ans.pop_back(); } cout << ans << endl; } }
def cal(s): n = len(s) arr = [n] * n stack = [] for i in range(n - 1, -1, -1): if stack: while stack and s[stack[-1]] >= s[i]: stack.pop() if stack: arr[i] = stack[-1] stack.append(i) return arr t = int(input()) for _ in range(t): n, m = list(map(int, input().split())) s = input() arr = cal(s) res = [] i = 0 while i < n: if m == 0: res.append(s[i]) i += 1 else: d = arr[i] - i if d > m: res.append(s[i]) i += 1 else: m -= d i = arr[i] print(''.join(res))
#include<bits/stdc++.h> using namespace std; int main(){ int T; cin>>T; while(T--){ int n,m; cin>>n>>m; string in; cin>>in; stack<char> tmp; int deleteNumber = 0; for (int i = 0;i<in.length();i++){ char x = in[i]; while(!tmp.empty() && x<tmp.top() && deleteNumber<m){ tmp.pop(); deleteNumber++; } tmp.push(x); } string result; while(!tmp.empty()){ result+=tmp.top(); tmp.pop(); } reverse(result.begin(),result.end()); cout<<result.substr(0,n-m)<<endl; } return 0; }