【uva 11491】Erasing and Winning（算法效率--贪心+单调队列）

题意：有一个N位整数，要求输出删除其中D个数字之后的最大整数。

解法：贪心。（P.S.要小心，我WA了2次...）由于规定了整数的位数，那么我们要尽量让高位的数字大一些，也就是要尽量删去前面小的数字。于是我们得到的数字前面是有一串下降的单调队列的，所以最开始就要维护这个。但是要注意——我们不是立马得到了这 n-d 位的整数，而是经过维护单调队列调整后的。因此我下面代码的那句break出循环是错的。

 1 #include<cstdio>

 2 #include<cstdlib>

 3 #include<iostream>

 4 using namespace std;

 5

 6 const int N=(int)1e5+10;

 7 int a[N];

 8

 9 int main()

10 {

11     while (1)

12     {

13       int n,d;

14       scanf("%d%d",&n,&d);

15       if (!n&&!d) break;

16       char c=getchar();

17       int t,cnt;

18       t=0;

19       while (c<'0'||c>'9') c=getchar();

20       while (c>='0'&&c<='9') a[++t]=c-'0', c=getchar();

21       t=1, cnt=0;

22       for (int i=2;i<=n;i++)

23       {

24         while (a[i]>a[t] && t>0 && cnt<d) t--,cnt++;

25         //if (t==n-d) break;//删d个，不能直接把后面的删了

26         a[++t]=a[i];

27       }

28       for (int i=1;i<=n-d;i++) printf("%d",a[i]);

29       printf("\n");

30     }

31     return 0;

32 }

巴特西

【uva 11491】Erasing and Winning（算法效率--贪心+单调队列）

最新文章

热门文章