本文主要是介绍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+鸽巢原理)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!