没看出来我哪里加空格了
题解被打回，两次原因分别为：
【中文标点符号】与【英文、数字、公式或汉字】或【汉字】与【汉字】之间不应添加多余空格。。
数学公式外应使用中文全角标点；句子末尾应添加句号，且全文使用的句号应一致；【中文】与【英文、数字或公式】之间应以半角空格隔开。。
双倍经验：[类似题目](https://www.luogu.com.cn/problem/P1106)
注意：代码相似，但是有些细节不一样。
## [本题传送门](https://www.luogu.com.cn/problem/CF1765N)
## 贪心思路：
每次从前往后扫，保证扫过的是不下降的，直到扫到第一个下降的，记为 $j$ 此时删除 $j$。
需要注意的是，要保证如果 $j$ 是当前字符串的第一个，那 $j$ 的后面不能是 $0$，否则会出现前导 $0$。
这一点在上面提到的类似题目中是允许的，但在本题中是不允许的。（~~重点敲黑板~~）
## 贪心证明:
我们想使得到的数尽可能的小，就需要尽可能的删**既靠前数字又大的**，如果前面 $n$ 个数是**不下降的**，就没必要删去。
如果删去这 $n$ 中的任意一个数（比如第 $i$ 位的数）我们直到第 $i+1$ 位的数肯定大于等于 $i$ 位的数，所以删去后得到的新数肯定是不优的。
按照这个想法，我们就要找到第一个违背了不下降的那个数 $j$ 并删去它。
## 代码1：
```cpp
#include<bits/stdc++.h>
using namespace std;
int t;//多测是真可爱(恶心),我讨厌多测
string a;//存数的
int k;//删k个
int main()
{
cin>>t;
while(t--)
{
cin>>a;
cin>>k;
for(int i=1;i<=k;i++)//删k个数
{
int j=0;
for(j=0;;j++)//从前往后扫,一直扫到满足if为止
{
if(a[j]>a[j+1] && (a[j+1]!='0' || j!=0))//前面a[j]>a[j+1]判断是否违背了不下降,后面判断前导0,要么满足后面不是0,要么不在第一位
{
break;//满足条件，跳出
}
}
a.erase(j,1);//也是看了dalao的才学会,可以用来删a字符串的第j个字符
}
cout<<a<<endl;//输出,虽然大家都懂但是我话多
}
return 0;
}
以上代码的最坏的时间复杂度是 O(nk) ，很明显会 TLE ，所以我们需要对它进行优化。
优化思路：
在我们删除了第 j 个数后，下一次循环中第 1 到第 j−1 的数我们还是要再扫一遍，但是我们在已经知道了这 j−1 个数是满足不下降的，所以我们下一次遍历可以直接从 j−1 开始。（注意不是 j ）
我们再开一个变量 p 用来储存下一次遍历开始的位置，p 值的更新应该在每一次删除第 j 个数后更新为 j−1，初始化为 0。
代码2:
#include<bits/stdc++.h>
using namespace std;
int t;//多测是真可爱(恶心),我讨厌多测
string a;//存数的
int k;//删k个
int main()
{
cin>>t;
while(t--)
{
cin>>a;
cin>>k;
int p=0;//每次从p开始遍历
for(int i=1;i<=k;i++)//删k个数
{
int j=0;
for(j=p;;j++)//从前往后扫,一直扫到满足if为止
{
if(a[j]>a[j+1] && (a[j+1]!='0' || j!=0))//前面a[j]>a[j+1]判断是否违背了不下降,后面判断前导0,要么满足后面不是0,要么不在第一位
{
break;//满足条件,跳出
}
}
a.erase(j,1);//也是看了dalao的才学会,可以用来删a字符串的第j个字符
p=j-1;//更新p的值
}
cout<<a<<endl;//输出,虽然大家都懂但是我话多
}
return 0;
}
优化后的时间复杂度是 O(n+k)，可以接受。
不是 O(n) 因为每个 j−1 都遍历了两遍。
管理大大给过吧求求了。
双倍经验：[类似题目](https://www.luogu.com.cn/problem/P1106)
注意：代码相似，但是有些细节不一样。
## [本题传送门](https://www.luogu.com.cn/problem/CF1765N)
## 贪心思路：
每次从前往后扫，保证扫过的是不下降的，直到扫到第一个下降的，记为 $j$ 此时删除 $j$。
需要注意的是，要保证如果 $j$ 是当前字符串的第一个，那 $j$ 的后面不能是 $0$，否则会出现前导 $0$。
这一点在上面提到的类似题目中是允许的，但在本题中是不允许的。（~~重点敲黑板~~）
## 贪心证明:
我们想使得到的数尽可能的小，就需要尽可能的删**既靠前数字又大的**，如果前面 $n$ 个数是**不下降的**，就没必要删去。
如果删去这 $n$ 中的任意一个数（比如第 $i$ 位的数）我们直到第 $i+1$ 位的数肯定大于等于 $i$ 位的数，所以删去后得到的新数肯定是不优的。
按照这个想法，我们就要找到第一个违背了不下降的那个数 $j$ 并删去它。
## 代码1：
```cpp
#include<bits/stdc++.h>
using namespace std;
int t;//多测是真可爱(恶心),我讨厌多测
string a;//存数的
int k;//删k个
int main()
{
cin>>t;
while(t--)
{
cin>>a;
cin>>k;
for(int i=1;i<=k;i++)//删k个数
{
int j=0;
for(j=0;;j++)//从前往后扫,一直扫到满足if为止
{
if(a[j]>a[j+1] && (a[j+1]!='0' || j!=0))//前面a[j]>a[j+1]判断是否违背了不下降,后面判断前导0,要么满足后面不是0,要么不在第一位
{
break;//满足条件，跳出
}
}
a.erase(j,1);//也是看了dalao的才学会,可以用来删a字符串的第j个字符
}
cout<<a<<endl;//输出,虽然大家都懂但是我话多
}
return 0;
}
以上代码的最坏的时间复杂度是 O(nk) ，很明显会 TLE ，所以我们需要对它进行优化。
优化思路：
在我们删除了第 j 个数后，下一次循环中第 1 到第 j−1 的数我们还是要再扫一遍，但是我们在已经知道了这 j−1 个数是满足不下降的，所以我们下一次遍历可以直接从 j−1 开始。（注意不是 j ）
我们再开一个变量 p 用来储存下一次遍历开始的位置，p 值的更新应该在每一次删除第 j 个数后更新为 j−1，初始化为 0。
代码2:
#include<bits/stdc++.h>
using namespace std;
int t;//多测是真可爱(恶心),我讨厌多测
string a;//存数的
int k;//删k个
int main()
{
cin>>t;
while(t--)
{
cin>>a;
cin>>k;
int p=0;//每次从p开始遍历
for(int i=1;i<=k;i++)//删k个数
{
int j=0;
for(j=p;;j++)//从前往后扫,一直扫到满足if为止
{
if(a[j]>a[j+1] && (a[j+1]!='0' || j!=0))//前面a[j]>a[j+1]判断是否违背了不下降,后面判断前导0,要么满足后面不是0,要么不在第一位
{
break;//满足条件,跳出
}
}
a.erase(j,1);//也是看了dalao的才学会,可以用来删a字符串的第j个字符
p=j-1;//更新p的值
}
cout<<a<<endl;//输出,虽然大家都懂但是我话多
}
return 0;
}
优化后的时间复杂度是 O(n+k)，可以接受。
不是 O(n) 因为每个 j−1 都遍历了两遍。
管理大大给过吧求求了。
哪里不符合要求啊,服了
加载中...