紫书 习题8-4 UVa 11491 （贪心）
2024-10-01 14:44:33
题意：给你一个数， 要求删去一些数字， 使得剩下的数字最大。
这道题用贪心解决。
大家想一想， 两个数比较大小， 肯定先比较第一位的数，然后依次比较第二位，以此类推。
既然我们要保证最后的数字最大， 那么一定要先保证第一位数的最大， 然后保证第二位数最大，以此类推。
所以贪心策略就是在能删除的范围内选择最大的数字，把最大的数字之前的数字删除， 把最大的数字留在最前面
然后一直这么做下去就ok了。
比如3759， 能删两个数。也就是说第一位要不是3要不是7要不是5， 7最大， 所以保留7， 删去3。然后
还能删去1个数字。目前的数字是759， 7已经确定为第一位了，不理它，现在确定第二位。
只能删一个数的时候， 第二位要不是5要不是是9， 留下9删去5.
所以答案是79.
#include<cstdio>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;
const int MAXN = 112345;
int a[MAXN], n, d;
int main()
{
while(~scanf("%d%d", &n, &d) && n && d)
{
REP(i, 0, n) scanf("%1d", &a[i]);
int temp = d;
int pos = 0;
while(d > 0 && pos < n) //pos < n 不能省去， 不然会RE
{
int ma = -1, t = pos;
REP(i, t, t + d + 1)
if(a[i] > ma)
{
pos = i;
ma = a[i];
}
REP(i, t, pos) a[i] = -1, d--;
pos++; //删完后从下一位开始继续找
}
int num = n - temp;
REP(i, 0, n)
if(a[i] != -1)
{
printf("%d", a[i]);
num--;
if(num == 0) break; //一共只能有n-d个数， 剩下的不要
}
puts("");
}
return 0;
}最新文章
- [原创]基于rsync算法的目的性改进-RexSync
- 结构体快排回顾（sort）
- 微信开发笔记（一）通过.net如何实现接入微信
- CMake with Win&MinGW
- EJB3Persistence开发手册-原生SQL查询(NativeSQL)
- 不只是打车软件，中国车主们赋予了Uber更多意义
- 基于ARM-LINUX的温度传感器驱动（DS18B20） .
- CNN(卷积神经网络)、RNN(循环神经网络)、DNN(深度神经网络)的内部网络结构有什么区别？
- Developing your first FNC custom control
- dump报文转换为wrieshark报文
- tap是什么意思
- Android SDK教程
- python的__init__几种方法总结
- 关于字符latin capital letter sharp s "ß"（ U+1E9E）显示的问题
- leetcode — spiral-matrix-ii
- 3张表实现RBAC
- Oracle HAVING子句 - 转
- MyBatis基础入门《十八》动态SQL(if-where)
- 关于c++输出中的endl
- 使用node连接MongoDB数据 综本地及linux服务器记