求解贪心思路是否正确
查看原帖
求解贪心思路是否正确
1017495
chenhaiyang楼主2024/6/8 12:01

贪心思路:对s串进行一个单调增处理

  • 即:
  • 187694 删1位->17694
  • 187694 删2位->1694
  • 187694 删3位->164
  • 187694 删4位->14
  • 下标i=1,j=0开始 利用双指针一直往前面找 如果s[j]大于s[i] 那么j-- 就是遍历到i下标时 i前面的数都是有序的。然后有判断删到k个数了我就停下了

我这个思路在这个平台过了 但是在另外一个平台没有过 求解答

#include <iostream>
using namespace std;

int main(){
    string s;
    int n;
    cin>>s>>n;
    int tmp=n;
    //单增
    for(int i=1,j=0;i<s.size();i++){
    	while(s[j]>s[i]&&tmp){
    		s[j]='x';
    		tmp--;
    		while(j>=0&&s[j]=='x')j--;
		}
		j=i;
    }
    
    //输出
    int t=s.size()-n;
    int flag=1;
    for(int i=0;i<s.size();i++){
    	if(s[i]=='0'&&flag)continue;

    	if(s[i]!='x'&&t){
    	    flag=0;
    		t--;
    		cout << s[i];
		}
	}
	if(flag)cout <<0; 
	return 0;
}

2024/6/8 12:01
加载中...