H.模拟
基础知识
什么是模拟？
模拟一个很宽泛的内容，比如字符串处理，日期处理。凡是不是很复杂但是没有标准归类的题目都可以称为模拟。
枚举和模拟是没有什么算法可言的，按照题目说的意思去模拟一下即可，要求对语法代码的熟练度比较高。
模拟题是有唯一解的，而不是求最优解的问题，只不过模拟题实现起来比较麻烦
例题
一、特别数的和
1.解题思路
就是一个简单的分离数位
模板1：
while(x)
{
int t=x%10;//取出x的个位
x=x/10;//删掉x的个位
}
模板2：
for(int i=x%10;x!=0;x=x/10,i=x%10)
{
}
2.代码
#include <iostream>
using namespace std;
int f(int x)
{
bool flag=false;
while(x)
{
int t=x%10;//取出x的个位
if(t==2||t==0||t==1||t==9)
{
flag=true;
break;
}
x=x/10;//删掉x的个位
}
if(flag) return 1;
else return 0;
}
int main()
{
int n;
cin>>n;
int ans=0;
for(int i=1;i<=n;i++)
{
if(f(i)==1) ans+=i;
}
cout<<ans;
return 0;
}
#include <iostream>
using namespace std;
int f(int x)
{
bool flag=false;
for(int i=x%10;x!=0;x=x/10,i=x%10)
{
if(i==2||i==0||i==1||i==9)
{
flag=true;
break;
}
}
if(flag) return 1;
else return 0;
}
int main()
{
int n;
cin>>n;
int ans=0;
for(int i=1;i<=n;i++)
{
if(f(i)==1) ans+=i;
}
cout<<ans;
return 0;
}
二、错误票据
1.解题思路
步骤：
①输入：都输入到一个数组中
本题比较坑的是注意输入，只告诉了有多少行，没告诉每行有多少个数。每行有多少个数需要自己处理 。
int a[100010];
int k=0;
int x;
while(cin>>x) //这行会把每个出现的数都存到a[]数组中
{
a[k++]=x;
}
②从小到大排序
③循环遍历数组
找重号：如果相邻两个数相等，那么这个就是重号
找断号 ：如果相邻的两个数相差2，那么两数中间的就是断号
2.代码
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 10010;
int n;
int a[N];
int main()
{
int cnt;
cin >> cnt;
string line;
getline(cin, line); // 忽略掉第一行的回车
while (cnt -- )
{
getline(cin, line);
stringstream ssin(line);
while (ssin >> a[n]) n ++ ;
}
sort(a, a + n);
int res1, res2;
for (int i = 1; i < n; i ++ )
if (a[i] == a[i - 1]) res2 = a[i]; // 重号
else if (a[i] >= a[i - 1] + 2) res1 = a[i] - 1; // 断号
cout << res1 << ' ' << res2 << endl;
return 0;
}
//另一种方法：暴力模拟法
#include <iostream>
#include <algorithm>
using namespace std;
int a[100010];
int main()
{
int n;
cin>>n;
int k=0;
//第一步：输入数据，合并到一个数组中
int x;
while(cin>>x)
{
a[k++]=x;
}
// for(int i=0;i<k;i++) cout<<a[i]<<" ";
//第二步：排序
sort(a,a+k);
//第三步：求重号：利用桶的思想，找到第一个重复的数据，记录
int t[100010],ans2=0;
for(int i=0;i<k;i++)
{
t[a[i]]++;
}
for(int i=0;i<=100000;i++)
{
if(t[i]>=2)
{
ans2=i;
break;
}
}
//第四步：求断号：先给序列去重，再利用下标和排好序的序列，找断号，注意边界
int z[100010],j=0;
for(int i=0;i<k;i++)
{
if(a[i]==a[i-1]) continue;
else z[j++]=a[i];
}
//for(int i=0;i<j;i++) cout<<z[i]<<" ";
int q=z[0],ans1=0;
for(int i=0;i<j;i++)
{
if(z[i]==q)
{
q++;
continue;
}
else
{
ans1=q;
break;
}
}
cout<<ans1<<" "<<ans2;
return 0;
}
三、移动距离
1.解题思路
题目中遇到距离一般有两种：曼哈顿距离 和 欧几里得距离
曼哈顿距离：|x1-x2|+|y1-y2| 两点之间走过的折线距离
欧几里得距离：sqrt((x1-x2) * (x1-x2)+(y1-y2) * (y1-y2)) 两点间的直线距离
本题所有点的坐标其实就是行号和列号
可以借鉴c++中二维数组的行号和列号下标表示：让编号从0开始标号，所以让m，n一开始都-1，不需要特判边界了。所以 行号：n/w m/w ，列号：n%w m%w
又因为本题编号是蛇形递增+1的，所以只需要判断是奇数行还是偶数行
偶数行不用变，奇数行逆序：if n/w 是奇数 ，w-1-n%w
2.代码
//时间复杂度O(1)
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int w, m, n;
cin >> w >> m >> n;
m --, n -- ; //让编号从0开始
int x1 = m / w, x2 = n / w; //两个点的行号
int y1 = m % w, y2 = n % w; //两个点的列号
if (x1 % 2) y1 = w - 1 - y1; //第一个点行号如果是奇数行，列号就反转一下
if (x2 % 2) y2 = w - 1 - y2; //第二个点行号如果是奇数行，列号就反转一下
cout << abs(x1 - x2) + abs(y1 - y2) << endl; //求出两点之间的曼哈顿距离
return 0;
}
四、航班时间
1.解题思路
通过分析，可以得到：
飞行时间=[(去的结束时间-去的起始时间)+(回的结束时间-回的起始时间)]/2
步骤：
①字符串格式化输入：这道题目麻烦就是麻烦在字符串的格式处理上
getline(cin,line);//忽略第一行的回车
int fh1,fm1,fs1,fh2,fm2,fs2,fd=0;
scanf("%d:%d:%d %d:%d:%d (+%d)",&fh1,&fm1,&fs1,&fh2,&fm2,&fs2,&fd);//注意输入时(+%d)，不匹配后就会跳过了
②将所有时间转化为距离当天00:00:00的秒数，得到飞行时间秒数time
int time1,time2,t;
time1=fd*24*3600+fh2*3600+fm2*60+fs2-(fh1*3600+fm1*60+fs1);
time2=ed*24*3600+eh2*3600+em2*60+es2-(eh1*3600+em1*60+es1);
t=(time1+time2)/2;
③再将飞行时间time转化为00:00:00这一规定时间格式：
hour=time/3600;
minute=time%3600/60
second=time%3600%60
④格式化输出：
printf("%02d:%02d:%02d\n", t/3600, t%3600/60, t%3600%60);
2.代码
#include<iostream>
#include <cstdio>
using namespace std;
int main()
{
int n;
cin>>n;
while(n--)
{
//输入去的时候起始时间和结束时间
int fh1,fm1,fs1,fh2,fm2,fs2,fd=0;
scanf("%d:%d:%d %d:%d:%d (+%d)",&fh1,&fm1,&fs1,&fh2,&fm2,&fs2,&fd);
//输入回的时候起始时间和结束时间
int eh1,em1,es1,eh2,em2,es2,ed=0;
scanf("%d:%d:%d %d:%d:%d (+%d)",&eh1,&em1,&es1,&eh2,&em2,&es2,&ed);
//计算两次分别的飞行时间，和除以2为最终的飞行时间
int time1,time2,t;
time1=fd*24*3600+fh2*3600+fm2*60+fs2-(fh1*3600+fm1*60+fs1);
time2=ed*24*3600+eh2*3600+em2*60+es2-(eh1*3600+em1*60+es1);
t=(time1+time2)/2;
//将秒数转化为规定格式输出
printf("%02d:%02d:%02d\n", t/3600, t%3600/60, t%3600%60);
}
return 0;
}
//封装为函数
#include<iostream>
#include<cstdio>
using namespace std;
int getTime()
{
int h1,m1,s1,h2,m2,s2,d=0;
scanf("%d:%d:%d %d:%d:%d (+%d)",&h1,&m1,&s1,&h2,&m2,&s2,&d);
int time=d*24*3600+h2*3600+m2*60+s2-(h1*3600+m1*60+s1);
return time;
}
int main()
{
int t;
scanf("%d",&t);
for(int i = 0; i < t; i++)
{
int time1=getTime();
int time2=getTime();
int t=(time1+time2)/2;
printf("%02d:%02d:%02d\n", t/3600, t/60%60, t%60);
}
return 0;
}
五、外卖优先级
1.解题思路
伪代码如下：
score[i]:表示第i个店铺当前的优先级
last[i]: 表示第i个店铺上一次有订单的时刻
st[i]:表示第i个店铺当前是否处于优先缓存中
将所有订单按时间顺序排序;
for 每个订单
{
每次处理一批相同的订单;
id,t,cnt;
//第一部分，是上一个拿到订单的时间last[id]和t之间，中间没订单所以要−1，没订单的数量是t−last[i]−1 (比如第3和第6时刻都有订单，没有订单的时候就是4,5)
score[id]=t-last[id]-1;
if(score[id]<0) score[id]=0;//计算优先权，如果为负值更新为0。如果小于等于3，更新优先缓存 st[id]=false
if(score[id]<=3) st[id]=false;
//第二部分，是此时，tt时刻拿到订单，并且拿到的数量为cntcnt，要加上2∗cnt
score[id]+=cnt*2;
if(score[id]>5) st[id]=true;//计算优先权，如果大于5，更新优先缓存 st[id]=true
}
for(int i=1;i<=n;i++)
{
if(last[i]<T)
{
score[i]-=T-last[i];
if (score[i] <= 3) st[i] = false;
}
}
res = 0;
for(int i=1;i<=n;i++)
{
res+=st[i];
}
2.代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 100010;
int n, m, T;
int score[N], last[N];
bool st[N];
PII order[N];
int main()
{
scanf("%d%d%d", &n, &m, &T);
for (int i = 0; i < m; i ++ ) scanf("%d%d", &order[i].x, &order[i].y);
sort(order, order + m);
for (int i = 0; i < m;)
{
int j = i;
while (j < m && order[j] == order[i]) j ++ ;
int t = order[i].x, id = order[i].y, cnt = j - i;
i = j;
/*
while (j < m && order[j] == order[i]) j ++ ;和cnt = j - i;是为了算出来同一时刻同一家店的订单数量，数量就是cnt的值，这个数量可能不唯一。
第一次while()循环中的order[j] == order[i]是一定成立的，然后j ++，j 就变成 i + 1，再比较order[i]和order[i + 1]是否相等，含义就是下一个订单与当前这个订单是不是同一时刻同一家店的，直到时刻或者 id 不同时，结束while循环，最后 j 就指向“不重复”的第一个订单，然后令 i = j，继续枚举所有订单
写成：int j = i + 1;，其它语句都不改动，也是对的，我感觉更好理解
*/
score[id] -= t - last[id] - 1;
if (score[id] < 0) score[id] = 0;
if (score[id] <= 3) st[id] = false;
score[id] += cnt * 2;
if (score[id] > 5) st[id] = true;
last[id] = t;
}
for (int i = 1; i <= n; i ++ )
if (last[i] < T)
{
score[i] -= T - last[i];
if (score[i] <= 3) st[i] = false;
}
int res = 0;
for (int i = 1; i <= n; i ++ ) res += st[i];
printf("%d\n", res);
return 0;
}
CSDN链接：https://blog.csdn.net/qq_46009744/article/details/124038527?spm=1001.2014.3001.5502
