心得体会：模拟法

要说到我个人最喜欢的几种解题方法，那模拟法肯定是其中之一

因为模拟法很简单，很无脑。不用想题想的浑身难受，只需要按照题目要求设定好规则，然后就撒手不管了。就像遗传算法只需要设定好“遗传变异”、“优胜劣汰”的规则，然后怎么进化都是程序的事儿，我们吃瓜就行了

有两种题可能会用到模拟法，一种是很直观的直接告诉你一堆规则 ，然后疯狂暗示就怕你不模拟 的，另一种是藏得比较深而且你不用模拟法也能做的（换句话说就是可以用模拟法偷懒而已）这里举几个典型的例子

---

例题一：逃跑的蠕虫（青蛙爬井类问题）（很明显可以用模拟法的一类）

题目链接：http://acm.swust.edu.cn/#/problems/281/374?_k=wwkqhs

题目：
装在瓶子的蠕虫都想从瓶子底部向瓶口处爬出去。它每分钟向上爬行u厘米，之后会休息一分钟，这一分钟它会向下滑行d厘米，当蠕虫到了瓶口或者超出瓶口后便出了瓶口，成功逃离（每分钟计算一次位置）。编写一个函数，帮助蠕虫计算它在什么时候能够爬出瓶子。

输入：
连续输入多个的实例，每一个实例输入三个正整数分别代表n，u和d，其中d < n ，n < 1000，当输入三个0时表明输入停止。

输出：
针对每一个输入实例，计算蠕虫跑出瓶子的时间。

样例输入：

10 2 1
20 3 1
0 0 0

样例输出：

17
19

---

分析：这题小学生都知道有个坑，但是由于我们懒，所以管他有啥坑哦，只要不T，模拟走起！首先分析，虫有两个动作，一是向上爬，二是向下掉，每个动作分别花1分钟的时间。那好，我就以时间为单位，一分钟一分钟的让程序去推演，每次推演看看虫子爬出去没有，爬出去了就返回推演到了多少分钟就行了，代码如下：

#include <stdio.h>
int func(int n,int u,int d);
int main()
{
	int n,u,d;
	while(scanf("%d%d%d",&n,&u,&d)!=EOF)
	{
		if(n==0&&u==n&&u==d)
		{
			break;
		}
		printf("%d\n",func(n,u,d));
	}
	return 0;
}
int func(int n,int u,int d)    
{
	int location=0,time=0,action=0;    //action用于控制虫子的动作，location记录虫子的位置，time就是当前时间
	while(location<n)       //只要虫子的位置小于瓶子的高度，继续爬
	{
		time++;             //时间流逝
		if(action==0)
		{
			location+=u;    //上爬u厘米
			action=1;       //下次进行下滑动作
		}
		else
		{
			location-=d;    //下滑d厘米
			action=0;       //下次进行上爬动作
		}
	}
	return time;       //爬出来了，返回时间
}

看完了代码，是不是觉得很简单很无脑呢？把规则设定好，推演的工作交给程序完成就是了，也不会遇到那个坑了。两三下照着题目的要求把代码搓出来，提交试一下，A了，皆大欢喜；T了 Σ(ﾟдﾟ;)…那还是推公式吧…后台可能有防模拟法的测试数据…

---

例题二：电影节（部分地方可以用模拟的思想的一类）

题目链接：http://scpc.openjudge.cn/2018train/15/

题目：
大学生电影节在北大举办! 这天，在北大各地放了多部电影，给定每部电影的放映时间区间，区间重叠的电影不可能同时看（端点可以重合），问李雷最多可以看多少部电影。

输入：
多组数据。每组数据开头是n(n<=100)，表示共n场电影。
接下来n行，每行两个整数(0到1000之间)，表示一场电影的放映区间
n=0则数据结束

输出：
对每组数据输出最多能看几部电影

样例输入：

8
3 4
0 7 
3 8 
15 19
15 20
10 15
8 18 
6 12 
0

样例输出：

3

---

分析：这其实也是一道贪心的经典例题，先按照结束时间从早到晚排序，然后从早到晚把不冲突的节目选出来就行了，不过嘛…怎么判断不冲突呢？等等，在你想一些骚操作之前，其实模拟一根时间轴就能解决，代码如下：

#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
struct movie
{
	int start,end;
};
int timeline[1001];      //这就是我们的时间轴！
int cmp(struct movie a,struct movie b)
{
	return a.end<b.end;
}
int isfree(struct movie a)   //判断当前电影时间内时间轴是否为空
{
	for(int i=a.start;i<a.end;i++)   //从电影开始时间起遍历时间轴
	{
		if(timeline[i]!=0) return 0;  //如果存在非0值，说明时间轴被占用，返回假，没空
	}
	return 1;    //时间轴没被占用，返回真，有空
}
void fill(struct movie a)  //填充时间轴
{
	for(int i=a.start;i<a.end;i++) timeline[i]=1;  //从电影开始时间起，到结束时间，把时间轴的值全部填为1
}
int main()
{
	int n;
	while(~scanf("%d",&n)&&n!=0)
	{
		struct movie list[n];
		for(int i=0;i<n;i++) scanf("%d%d",&list[i].start,&list[i].end); //接收数据
		sort(list,list+n,cmp);                //按照结束时间从早到晚排序
		memset(timeline,0,sizeof(timeline));  //清空时间轴
		int count=0;          //统计可以填入时间轴的电影总数
		for(int i=0;i<n;i++)  //遍历排序后的全部电影
		{
			if(isfree(list[i])==1)  //如果时间轴为空
			{
				count++;        //可以填入时间轴的电影数+1
				fill(list[i]);  //填入时间轴
			}
		}
		printf("%d\n",count);   //返回的count即为所有可以填入时间轴并且不冲突的电影数
	}
	return 0;
}

是不是通过模拟一根时间轴就可以很简单的把电影时间之间的冲突判断问题解决了呢？而且理解起来是不是很直观很容易嘛…无脑搓完，提交！哎，没T，开心（
野生的大佬：胡说！你直接判断电影的开始时间是否大于上一个电影的结束时间不就完了吗！
我(瑟瑟发抖)：诶诶，锻炼一下思维嘛(´；ω；`)

总结：

有些题如果看起来很复杂，一时没有头绪，看一看输入的数据数量级以及程序时间限制，如果感觉不会T，而且有可以模拟的思路，不妨试试模拟法 ，万一A了呢对吧