HDU3183(RMQ+鸽巢原理)

本文主要是介绍HDU3183(RMQ+鸽巢原理)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目的意思是对于一个n位数，删除m个位后，得到的最小数是什么，比如12345 2,删除两个位，得到最小的就是123.实际上这题目解法很多，好像有贪心，线段树，RMQ等，因为我最近在学习RMQ，所以就用RMQ了。

这题目用了一个鸽巢原理,得到的m-n位数的第一位，必然出现在1~m-n+1,这个由鸽巢原理就十分明显了（如果1~n-(m-n)+1都没有的话，剩下的m-n-1个位是不可能凑出m-n个位的数的！）这样我们就可以从[1,n-(m-n)+1]中作RMQ取得最小值下标i,之后对于i+1后，m-n-1求第二个最小，依次递推即可。

我的RMQ写得很挫，唯有参考大神的代码了！

╮(╯▽╰)╭，身上有的东西基本都是从别人那里学来的，因为原创是很困难的。

/***********************************************************> OS     : Linux 3.2.0-60-generic #91-Ubuntu> Author : yaolong> Mail   : dengyaolong@yeah.net > Time   : 2014年06月06日 星期五 07:19:57**********************************************************/
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<cmath>
using namespace std;
int mmin[1234][20];
char str[12

这篇关于HDU3183(RMQ+鸽巢原理)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---