【c++入门（2）】模拟

所谓模拟，就是按照题目的意思将整个过程用代码一步步实现出来。

也就是一步步用代码完成题目中的任务，模拟有很多坑点，但又是比赛常考的题型。

核心就是刚才所讲的按照题目的意思进行 *** 作，来看看几道题目。

The Bovine Shuffle
Farmer John相信快乐的奶牛会产出更多的牛奶，所以FJ在牛棚中安装了一个迪斯科球，准备教他的奶牛们跳舞。

查找了一些比较流行的奶牛舞蹈后，FJ准备教他的奶牛们跳“Bovine Shuffle”(曳步舞)。


舞蹈是这样的：N(1≤N≤100)头奶牛按照一定顺序排成一排，然后进行三次“shuffles”，每次“shuffles”后，奶牛们将会被重新排列。


为了让奶牛们更容易找到自己的位置，FJ用1...N分别标记了N头奶牛的位置，队列中排第一的奶牛的位置是1，排第二的奶牛的位置是2，以此类推，排在第N位的奶牛的位置是N。


用N个整数a1,a2...,aN来描述一次“shuffles”，ai表示在位置i上的奶牛经过这次“shuffles”后，跑到了位置ai上。


每次“shuffles”，每头奶牛都会移动到新的位置上，而且所有的ai都不相同，所以“shuffles”期间，所有奶牛的位置都是不同的。


FJ的每头奶牛都有一个ID号，是一个7位的整数，给定三次“shuffles”后奶牛的顺序，请确定出他们初始时候的顺序。


输入格式

第一行，一个整数N，表示奶牛的数量
第二行，N个整数，表示a1,a2...,aN，描述一次“shuffles”
第三行，描述三次“shuffles”后，N头奶牛的顺序，每个整数表示一头奶牛的ID编号
输出格式

输出N行，每行一个奶牛ID号，输出三次“shuffles”前奶牛们的初始位置顺序。


输入输出样列
输入样例1：

5
1 3 4 5 2
1234567 2222222 3333333 4444444 5555555

输出样例1：

1234567
5555555
2222222
3333333
4444444

这道题我们对比一下前后的位置：
由此很容易得出a[i] = b[c[i]]。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

const int N = 110;
int n, a[N], b[N], c[N];

int main()
{


	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> c[i];
	}
	for (int i = 1; i <= n; i++)
	{
		cin >> b[i];
	}
	for (int i = 1; i <= 3; i++)
	{
		for (int j = 1; j <= n; j++) a[j] = b[c[j]];
		for (int j = 1; j <= n; j++) b[j] = a[j];
	}
	for (int i = 1; i <= n; i++)
	{
		cout << a[i] << endl;
	}


    return 0;
}

Blocked Billboard II
题目描述

奶牛Bessie从她的牛棚可以看到非常美丽的风景，她隔着马路看到了一组广告牌，展示的是奶牛饲料的广告，是一些看起来很美味的嫩草。

但不幸的是，其中的一个广告牌最近升级了，展示的是“Farmer Larry家的割草机”。



Bessie很不喜欢割草机，因为割草机的目的就是要把她认为如此美味的嫩草给割掉。



幸运的是，如果把剩下的奶牛饲料的广告牌放在割草机的广告牌前面，割草机的广告牌看起来就会不那么清晰了。



Bessie决定把那块令她讨厌的割草机广告牌从她的视线里完全抹去，于是她制定了一个冒险的计划。

她计划从牛棚偷一块长方形的防水布，深夜的时候偷偷溜出去，盖住割草机广告牌剩余的部分，这样她就再也不用看到了。



给定两个广告牌的位置，请帮助Bessie计算出她需要的防水布的最小面积。

由于牛棚中唯一可用的防水布是矩形的，所以Bessise发现她可能需要的防水布的面积比割草机广告牌暴露的面积略大（如样例所示）。



防水布放置时，它的侧边要与其他广告牌平行放置。


输入格式

第一行，用空格隔开的四个整数x1,y1,x2,y2.(x1,y1)和（x2,y2）分别表示割草机广告牌在Bessie二维视野中的左下角和右上角的坐标。



接下来一行，用空格隔开的四个整数，类似上一行，描述了奶牛饲料的广告牌的左下角和右上角的坐标。

奶牛饲料的广告牌可能遮盖了全部、部分割草机广告牌，或者是一点都没有遮盖。

所有整数的范围是-1000到1000
输出格式

请输出，Bessie需要用来遮盖割草机广告牌的防水布的最小面积。


输入输出样列
输入样例1：

2 1 7 4
5 -1 10 3

输出样例1：

15

说明

样例说明：

样例中，奶牛饲料的广告牌只遮盖了割草机广告牌的右下角，然而这并没有什么帮助。

所以Bessie还是需要一块与割草机广告牌一样大小的防水布。

所以防水布的面积是15.

红色代表割草机广告牌，蓝色代表奶牛饲料广告牌:
得出奶牛饲料广告牌至少需要覆盖割草机广告牌的三条边，才能减少防水布的使用！

想一想，上面的图中怎样计算所需防水布的面积？
(x2-x1) * (b1-y1)
dm我应该不需要写了吧。

公交换乘
题目描述

著名旅游城市 B 市为了鼓励大家采用公共交通方式出行，推出了一种地铁换乘公交 车的优惠方案： 

1. 在搭乘一次地铁后可以获得一张优惠票，有效期为 45 分钟，在有效期内可以消耗这张优惠票，

免费搭乘一次票价不超过地铁票价的公交车。

在有效期内指 开始乘公交车的时间与开始乘地铁的时间之差小于等于 45 分钟，

    即：   tbus-tsubway≤45 

2. 搭乘地铁获得的优惠票可以累积，即可以连续搭乘若干次地铁后再连续使用优 惠票搭乘公交车。

 

3. 搭乘公交车时，如果可以使用优惠票一定会使用优惠票；如果有多张优惠票满 足条件，则优先消耗获得最早的优惠票。

 

现在你得到了小轩最近的公共交通出行记录，你能帮他算算他的花费吗？ 
输入格式

输入文件名为 transfer.in。

  

输入文件的第一行包含一个正整数 n，代表乘车记录的数量。

  

接下来的n行，每行包含 3 个整数，相邻两数之间以一个空格分隔。



第i行的 第 1 个整数代表第i条记录乘坐的交通工具，0 代表地铁，1 代表公交车；

        第 2 个整数代表第i条记录乘车的票价pricei

        第 3 个整数代表第i条记录开始乘车的时间ti （距 0 时刻的分钟数）。

 

我们保证出行记录是按照开始乘车的时间顺序给出的，且不会有两次乘车记录出现在同一分钟。


输出格式

输出文件名为 transfer.out。

 

输出文件有一行，包含一个正整数，代表小轩出行的总花费 
输入输出样列
输入样例1：

6 
0 10 3 
1 5 46 
0 12 50 
1 3 96 
0 5 110 
1 6 135

输出样例1：

36

输入样例2：

6 
0 5 1 
0 20 16 
0 7 23 
1 18 31 
1 4 38 
1 7 68

输出样例2：

32

说明

【输入输出样例 1 说明】 

第一条记录，在第 3 分钟花费 10 元乘坐地铁。

 

第二条记录，在第 46 分钟乘坐公交车，可以使用第一条记录中乘坐地铁获得的优惠票，因此没有花费。

 

第三条记录，在第 50 分种花费 12 元乘坐地铁。

 

第四条记录，在第 96 分钟乘坐公交车，由于距离第三条记录中乘坐地铁已超过 45 分钟，所以优惠票已失效，花费 3元乘坐公交车。

 

第五条记录，在第 110 分钟花费 5 元乘坐地铁。

 

第六条记录，在第 135 分钟乘坐公交车，由于此时手中只有第五条记录中乘坐地铁获得的优惠票有效，而本次公交车的票价为6元，

高于第五条记录中地铁的票价 5 元， 所以不能使用优惠票，花费 6 元乘坐公交车。

 

总共花费 36 元



【输入输出样例 2 说明】 

第一条记录，在第 1 分钟花费 5 元乘坐地铁。

 

第二条记录，在第 16 分钟花费 20 元乘坐地铁。



第三条记录，在第 23 分钟花费 7 元乘坐地铁。

 

第四条记录，在第 31 分钟乘坐公交车，此时只有第二条记录中乘坐的地铁票价高于本次公交车票价，所以使用第二条记录中乘坐地铁获得的优惠票。

 

第五条记录，在第 38 分钟乘坐公交车，此时第一条和第三条记录中乘坐地铁获得的优惠票都可以使用，使用获得最早的优惠票，即第一条记录中乘坐地铁获得的优惠票。



第六条记录，在第 68 分钟乘坐公交车，使用第三条记录中乘坐地铁获得的优惠票。

 总共花费 32 元。




【数据规模与约定】  

 对于30%的数据，n≤ 1,000，ti≤ 10^6。

 

 另有 15% 的数据，ti≤ 10^7，pricei都相等。

 

 另有 15% 的数据，ti ≤ 10^9，pricei都相等。

  

 对于 100% 的数据，n ≤ 10^5，ti ≤ 10^9，1 ≤ pricei ≤ 1,000。

 
【耗时限制】1000ms 【内存限制】256MB 

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

const int N = 100000 + 5;
struct A
{
	int m;
	int t;
} a[N]; 
int ans;

int main(){
	int n;
	int p = 0, s = 1;
	cin >> n;
	for(int i = 1; i <= n; i++)
	{
		int c, m, t;
		cin >> c >> m >> t;
		if(c == 0)
		{
			a[++p].m = m;
			a[p].t = t;
			ans += m;
		}
		else
		{
			while (s <= p && t - a[s].t > 45) s++;
			bool aa = true;
			for(int j = s; j <= p; j++)
			{
				if(m <= a[j].m)
				{
					a[j].m = 0;
					aa = false;
					break;
				}
			}
			if(aa == true) ans += m;
		}
	}
	cout << ans;

	return 0;
}