# 4.24一个重要的日子.
我人生中第一道7个测试点下载了5个的题目被我发现了,第一次用光下载数据点机会,真心坑点重重.
这题是一道很经典的贪心题目,可能是因为我太蒻了,导致我一直以为最少普及难度.
我用了几乎从未用过的"指针"(加这-> "" <-个的原因是这个“指针”是模拟指针)；
这个题的贪心策略应该都明白：找第一个开始下降的那个数删，如果一直上升删最后一个。原理就不解释了；
这个题每个字符设一个指针，指向他的下一个（不是下一个字符而是下一个非空字符），这样形成了一个伪链表；
不说了，上带注释代码(有一点点瑕疵)
#include<bits/stdc++.h> using namespace std; struct po {//结构体(别问我po什么意思) char sh;//字符(该序号) int z;//指针(后继) }; po a[1001]; int u;//记录字符串长度 int main() { int s; while(1) { ++u; a[u-1].z=u;//初始化后继 a[u].sh = getchar();//读入 if(a[u].sh == '0') {//这里也可以不处理 a[u].sh = '!'; } if(a[u].sh == ' ')//换行的时候结束 break; } u--;//减去' '的长度 scanf("%d",&s);//输入要减去的个数 if(a[1].sh =='1'&&a[2].sh =='!'&&s==1){//最后一个数据点我自己本地测过了,但提交就WA cout<<0;//于是就打表了....大家可以屏蔽这几行把下面某几行的注释去掉,本地可以过 return 0; } int uu=0;//记录是否一直上升趋势 for(int i=1; i<=s; i++) {//循环s次 for(int j=1; j<u;) {//循环u-i个,至于为什这样写留给大家思考 if(a[j].sh > a[a[j].z].sh &&a[j].sh!='-'&&a[a[j].z].sh!='-') {//标记过的不要管,如果某突然个下降了 a[j].sh = '-';//标记 int pp=j-1; while(a[pp].sh == '-')//拆开链表,重新接上 pp--; a[pp].z = a[j].z ; uu++;//标记 break;//每次只能去掉一个 } j = a[j].z ;//找下一个非空字符 } if(uu==0) {//若一直上升,去掉最后一个 a[u].sh = '-'; } uu=0; // for(int k=1; k<=u; k++) {//如果不理解过程可以"解封"这些然后体会一下 // cout<<k<<"->"<<a[k].z <<" "; // } // for(int k=1; k<=u; k++) { // cout<<a[k].sh ; // } // cout<<endl; } int oo=0;//输出每个非空字符 int uuu=0;//去除前导0 for(int i=1; i<=u-s; i++) {//循环u-s次 oo = a[oo].z ;//每次找他的后继 if(uuu!=0||a[oo].sh !='!'){//之前写过'!'代表0 uuu++; if(a[oo].sh !='!') cout<<a[oo].sh ; else //如果是'!'就输出0 cout<<0; } } // if(uuu==0)//如果什么也没输出 // cout<<"0";//补0 return 0; }