hdu 3183 A Magic Lamp ( 暴力)
题意:n位长的数字串(n<=1000),删掉m个(m<=n),使得剩下的数字串表示的数字最小。 忽略前导0.
思路:暴力搞就可以。要注意每位数字是有一定位置的范围的。比如当前是第i位数字,后面还要取n-m-i位数字,那么第i位数字最多只能取到第k位,k=m+i,因为这样才能保证后面还有n-m-i位数字。
/* ***********************************************
Author :111qqz
Created Time :2016年05月16日 星期一 13时15分44秒
File Name :code/hdu/3183.cpp
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,int >
20#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const int N=1E3+7;
7int n,m;
1int ans[N];
2char st[N];
3int main()
4{
5 #ifndef ONLINE_JUDGE
6 freopen("code/in.txt","r",stdin);
7 #endif
1 while (~scanf("%s %d",st,&m))
2 {
3 n = strlen(st);
4 ms(ans,0);
1 int x = 0 ;
2 for ( int i = 1 ; i <= n-m ; i++)
3 {
4 int MIN = inf;
5 for ( int j = x+1 ; j <= m+i ; j++)
6 {
7 int val = st[j-1]-'0';
8 if (val<MIN)
9 {
10 MIN = val;
11 x = j;
12 }
13 }
14 ans[i] = MIN;
15 }
1 bool zero = true;
2 bool output = false;
3 for ( int i = 1; i <= n-m ; i++)
4 {
5 if (ans[i]!=0) zero = false;
6 if (!zero)
7 {
8 output = true;
9 printf("%d",ans[i]);
10 }
11 }
12 if (output)
13 printf("\n");
14 else printf("0\n");
}
1 #ifndef ONLINE_JUDGE
2 fclose(stdin);
3 #endif
4 return 0;
5}