1321: [example 6.3] deletion problem (noip1994)

1321：【 example 6.3】 Censoring problem (Noip1994)

The time limit : 1000 ms         Memory limit : 65536 KB
Submission number : 25868     Passing number : 9164

【 Title Description 】

Enter a high precision positive integer n, Remove any of them s The rest of the numbers after the first number form a new positive integer according to the original left and right order . Programming for a given n and s, Find a scheme to make the new number of the remaining numbers minimum .

Output a new positive integer .（n No more than 240 position ）

The input data do not need to be judged wrong .

【 Input 】

n

s

【 Output 】

The last remaining decimal .

【 sample input 】

175438
4

【 sample output 】

13

【 Algorithm analysis 】

greedy . loop s Time , Delete s A large number , The rest is the minimum .

【AC Code 】

#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
const int N=340;
char n[N];
int s,len,m,x;
signed main()
{
	scanf("%s%d",&n,&s);
	x=len=strlen(n);
	for(int i=1;i<=s;i++)
	{
		for(int j=0;j<len-1;j++)
			if(n[j]>n[j+1])// If the current number is greater than the next number 
			{
				for(int k=j;k<len-1;k++)n[k]=n[k+1];// Delete that number 
				break;// Out of the loop 
			}
		len--;// length -1
	}
	while(n[m]=='0' and x>1)m++,x--;// Remove the lead 0
	for(int i=m;i<len;i++)printf("%c",n[i]);
	return 0;
}

Pay attention to it

 

The time limit : 1000 ms         Memory limit : 65536 KB
Submission number : 25868     Passing number : 9164

【 Title Description 】

Enter a high precision positive integer n, Remove any of them s The rest of the numbers after the first number form a new positive integer according to the original left and right order . Programming for a given n and s, Find a scheme to make the new number of the remaining numbers minimum .

Output a new positive integer .（n No more than 240 position ）

The input data do not need to be judged wrong .

【 Input 】

n

s

【 Output 】

The last remaining decimal .

【 sample input 】

175438
4

【 sample output 】

13

【 Algorithm analysis 】

greedy . loop s Time , Delete s A large number , The rest is the minimum .

【AC Code 】

#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
const int N=340;
char n[N];
int s,len,m,x;
signed main()
{
	scanf("%s%d",&n,&s);
	x=len=strlen(n);
	for(int i=1;i<=s;i++)
	{
		for(int j=0;j<len-1;j++)
			if(n[j]>n[j+1])// If the current number is greater than the next number 
			{
				for(int k=j;k<len-1;k++)n[k]=n[k+1];// Delete that number 
				break;// Out of the loop 
			}
		len--;// length -1
	}
	while(n[m]=='0' and x>1)m++,x--;// Remove the lead 0
	for(int i=m;i<len;i++)printf("%c",n[i]);
	return 0;
}

Pay attention to it