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

admin管理员组

文章数量:815114

【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 <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <stack>
#include <list>
#include <limits.h>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 <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <stack>
#include <list>
#include <limits.h>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;
}

本文标签： c入门（2）模拟