| 题目名称 | 1018. [Clover S1] 数字游戏 |
|---|---|
| 输入输出 | gamec.in/out |
| 难度等级 | ★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 Makazeu
于2012-08-20加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：37， 提交：144， 通过率：25.69% | ||||
 Qw |
100 | 0.168 s | 28.92 MiB | C++ |
 Ezoi_XY |
100 | 0.185 s | 24.13 MiB | C++ |
 Dissolute丶Tokgo |
100 | 0.186 s | 24.16 MiB | C++ |
 test.in |
100 | 0.194 s | 24.13 MiB | C++ |
 Lee Sin |
100 | 0.199 s | 24.16 MiB | C++ |
 四季木哥 |
100 | 0.206 s | 24.13 MiB | C++ |
|
四季木哥 |
100 | 0.206 s | 24.13 MiB | C++ |
 sk_code |
100 | 0.209 s | 28.92 MiB | C++ |
 YZQ |
100 | 0.211 s | 28.90 MiB | C++ |
 一個人的雨 |
100 | 0.213 s | 24.13 MiB | C++ |
| 关于 数字游戏 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
数据结构使人懒惰....无脑敲了个线段树过了七个点
四季木哥
2015-09-18 09:38
4楼
| ||||
|
为什么本地测试是对的
| ||||
|
表示只想到了模拟链表……
| ||||
|
贪心策略为：从高位到低位扫描，若存在递减区间，则将高位删除以消除递减区间，否则从低位删。具体操作时，可以设一个栈来保存从高位起还没删的数。不难发现最后的结果一定是一个不下降序列，由此可以想到用二分来优化。
| ||||
HouJikan
苏轼【题目描述】
认识到了游泳的巨大安全隐患之后，小朋友们都决定不去游泳了。于是，游泳馆冷清了下来。为了能因时制宜、因事制宜，游泳馆决定在游泳项目之外，还开设头脑风暴项目。
头脑风暴当中有这样一道题目：
给出一个$LEN$位的数字$A$，你可以删除数字$A$当中的$N$位，删除之后得到一个$LEN-N$位的数字$B$，你的目标就是使这个数字$B$最小。
头脑风暴规定，第一名的选手可以获得奖品哦~还等什么，快来参加吧！
【输入格式】
第一行$LEN$位$0$~$9$的整数，表示数字$A$.
第二行一个整数$N$，表示你可以进行的删除操作的次数。
数据保证数字$A$没有前导$0$.
由于$LEN$可以从数字$A$间接得到，因此不直接给出$LEN$的大小。
【输出格式】
一行，表示数字$A$在一系列操作之后的最小值，即数字$B$.
如果数字$B$有前导$0$，请不要输出前导$0$.
特别地，如果数字$B$为$0$，请输出一个数字“$0$”（不含引号）.
【样例输入】
20131 3
【样例输出】
1
【样例说明】
样例解释：删掉数字$A$的第$1$ $3$ $4$位，得到数字$B$为“$01$”，去除前导$0$，输出$1$.
【数据规模与约定】
对于$50$%的数据，$LEN<=100000$.
对于$100$%的数据，$LEN<=5000000,0<=N<=LEN$.
【来源】
From - This_poet
Contact me - This_poet@126.com/Freda.RD.Shi@gmail.com
This_poet's Blog - http://thispoet.blogcn.com