hdu-3183A Magic Lamp（贪心）

题目的意思是：

给你一个大数，然后删减其中的K个数，并且剩下的数还是按原来在的先后次序排列，求所得的那个数最小的那个数。

思路：贪心（要取得数最小，你从左往右选数的时候，选的第一数，就是选后组成数的位权最高的，要一个数最小，位权最高的所对应那位要最小，然后依次是下一位权最小）。原来有N个数，删除K个数得最小数可以转化为从左往右选N-K个数所组成的数最小。那么第一个数必须在区间[0，K]（数组下标）(存大数的数组首位是从0开始的)。

证：选的第一位数如果超过K,假如取的是K+S(K+S<=N-1)那么从（K+S+1）到N-1还剩下（N-K-S-1）个数，因为已经选了一个数剩余（N-K-1）个数没选，那么这些数必定要在区间

[K-S+1,N]上选。又（N-K-1）大于区间长度N-K-S-1（S>=1）.

所以第一个数只能在[0,K]上取，且要取最小值，每位取当前区间最小才能保证最后所得数最小。

那么当第一个数取完后，取的是pos位置的，那么在[0,pos-1]是未取得数，也就是去掉的数，因为后面省下的（N-K-1）个数不能在这些位置去，因为这些数在pos之前，所以如果去的话

在所得的数中位置在第一个数之前，所以与pos为第一个数矛盾。

这样你选第二个数时此时K应该更新为K-(pos+1-n)(n为当前所选好的数的个数（当前n=1）),pos更新为pos+1；那么第二个数在区间[pos,pos+K]其实pos+K就为K+n;

那么这样直到选好N-K个数就行了。

 /*RMQ优化 复杂度为n*log(n)*/
 1 #include<stdio.h>

 2 #include<algorithm>

 3 #include<iostream>

 4 #include<stdlib.h>

 5 #include<string.h>

 6 #include<math.h>

 7 void RMQup(int k,int l);

 8 int que(int i,int j);

 9 int Min(int x,int y);

10 char a[2000];

11 int  b[2000];

12 const int N=100;

13 int RMQ[1005][1005];

14 using namespace std;

15 int main(void)

16 {

17     int n,i,j,k,p,q,l,m;

18     while(scanf("%s",a)!=EOF)

19     {

20         scanf("%d",&k);

21         l=strlen(a);

22         p=l-k;

23         for(i=0; i<l; i++)

24             RMQ[0][i]=i;

25         int r=log2(l);

26         r++;

27         RMQup(r,l);

28         int pp,qq;

29         int dd;

30         pp=0;

31         m=k;

32         int coutt =0;

33         while(coutt<p)//选好p个数字就结束

34         {

35             int z=que(pp,m);

36             b[coutt++]=a[z]-'0';

37             pp=z+1;

38             m++;

39         }

40         for(i=0; i<p; i++)

41         {

42             if(b[i]!=0)

43             {

44                 break;

45             }

46         }

47         for(j=i; j<p; j++)

48         {

49             printf("%d",b[j]);

50         }

51         if(i==p)

52         {

53             printf("0");

54         }

55         printf("\n");

56     }

57

58     return 0;

59

60

61 }

62

63

64 void RMQup(int k,int l)//dp求RMQ（这种RMQ链接讲解http://www.cnblogs.com/zzuli2sjy/p/4971449.html）

65 {

66     int i,j;

67     for(i=1; i<=k; i++)

68         for(j=0; j<l; j++)

69             if(j+(1<<i-1)<l)

70                 RMQ[i][j]=Min(RMQ[i-1][j],RMQ[i-1][j+(1<<i-1)]);

71

72 }

73

74 int que(int i,int j)

75 {

76     int f=log2(j-i+1);

77     return Min(RMQ[f][i],RMQ[f][j-(1<<f)+1]);

78

79 }

80 int Min(int x,int y)//求在某段的最小值的数组下标

81 {

82     if(a[x]==a[y])

83     {

84         return x<y?x:y;//当两个数相同时返回数组下标小的(比如223 要去1个数字，答案是22，如果返回数组下标大的结果就是23了)

85     }

86     else

87     {

88         return a[x]<a[y]?x:y;

89     }

90 }

 1 /*直接循环找段最小*/

 2 #include<stdio.h>

 3 #include<algorithm>

 4 #include<iostream>

 5 #include<stdlib.h>

 6 #include<string.h>

 7 using namespace std;

 8 char a[1005];

 9 char b[1005];

10 int main(void)

11 {

12     int n,i,j,k,p,q,l;

13     while(scanf("%s",a)!=EOF)

14     {

15         scanf("%d",&k);

16         l=strlen(a);

17         if(k==l)

18         {

19             printf("0\n");

20         }

21         else

22         {

23             int y=l-k;

24             int x=0;

25             int m=y;

26             int coutt=0;

27             int dd;

28             dd=0;

29             while(coutt<y)

30             {

31                 b[coutt]=a[x];

32                 for(i=x; i<=x+k; i++)//循环找最小

33                 {

34                     if(a[i]<b[coutt])

35                     {

36                         b[coutt]=a[i];

37                         dd=i;

38                     }

39

40                 }

41                 dd=dd+1;

42                 k-=(dd-x-1);

43                 coutt++;

44                 x=dd;

45             }

46             for(i=0; i<coutt; i++)

47             {

48                 if(b[i]!='0')

49                 {

50                     break;

51                 }

52             }

53             if(i==coutt)

54             {

55                 printf("0");

56             }

57             for(j=i; j<coutt; j++)

58             {

59                 printf("%c",b[j]);

60             }

61             printf("\n");

62         }

63     }

64     return 0;

65 }

巴特西

hdu-3183A Magic Lamp（贪心）

最新文章

热门文章