P1897 电梯里的爱情 [洛谷]

P1897 电梯里的爱情 [洛谷]

P1897 电梯里的爱情 [洛谷]

​​1.题目​​​​2.分析​​​​3.代码​​

​​1. 70分 TLE​​​​2. AC vector、erase、sort、unique​​​​3.priority_quque 优先队列 [方便获取最大值]​​

​​注：该方法调用时，在VS中会报 front called on empty vector 错误，具体原因是调用top()时，会调用front(),为空时，不可调用front()​​

​​4.set 集合​​

​​注：set会自动排序、自动去重，同时注意如何取得set最后一个元素​​

​​4.总结​​​​5.更新日志​​

1.题目

题目描述

细心的同事发现，小 W 最近喜欢乘电梯上上下下，究其原因，也许只有小W自己知道：在电梯里经常可以遇到他心中的女神 PR。

这是个很简单的问题，要知道，小 W 已经修炼到快速心算出结果的境界，现在你来编程试试吧！

输入格式

输出格式

样例输入 #1

42 4 3 2

样例输出 #1

59

提示

2.分析

总时间= 电梯上下运行 + 开门时间 + 上下时间电梯上下运行 = max（层数）❌10 开门时间 = 不同层数 ❌ 5 上下时间 = 人数[set挺合适的~不过最开始没想到]

3.代码

1. 70分 TLE

#include using namespace std;#include #include //find();typedef vector VI;typedef long long LL;int main(){ int n; scanf("%d", &n); VI difs; int maxn = 0; for (int i = 0; i < n; ++i) { int t; scanf("%d", &t); maxn = max(maxn, t); auto res = find(difs.begin(), difs.end(), t); if (res == difs.end()) difs.push_back(t); } LL res = 10 * maxn + 5 * difs.size() + n; printf("%lld", res); return 0;}

原因分析：find函数，较为缓慢

2. AC vector、erase、sort、unique

前置知识：​​​erase（）、unique（）函数​​

#include using namespace std;#include //sort#include //vectortypedef long long LL;typedef vector VI;//res只与maxn与difs.size()有关，则直接排序去重即可int main(){ int n; scanf("%d", &n); VI difs; //存储 不同的楼层个数 int maxn = 0; for (int i = 0; i < n; i++) { int t; scanf("%d", &t); maxn = max(maxn, t); difs.push_back(t); } sort(difs.begin(), difs.end()); //排序 difs.erase(unique(difs.begin(), difs.end()), difs.end()); //去重 LL res = 10 * maxn + 5 * difs.size() + n; printf("%lld", res); return 0;}

3.priority_quque 优先队列 [方便获取最大值]

速度慢了很多，内存占用也挺多

#include using namespace std;#include //priority_queue#include //sort;typedef priority_queue PQI;typedef long long LL;PQI fls; //优先队列，默认大根堆，即最大值即为顶inline int read(){ int x = 0, f = 1; char ch = getchar(); while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); } while (isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); } return x * f;}int ttime(int x){ int t = 5; while (fls-() == x && fls.size()) t++, fls.pop(); return t;}int main(){ int n; scanf("%d", &n); //读入所有楼层 for (int i = 0; i < n; ++i) fls.push(read()); //上下楼运行时间 LL res = 10 * fls-(); //开门+出门 while (fls.size()) res += ttime(fls-()); printf("%lld", res); return 0;}

注：该方法调用时，在VS中会报 front called on empty vector 错误，具体原因是调用top()时，会调用front(),为空时，不可调用front()

4.set 集合

#include using namespace std;#include set fls;int main(){ int n; scanf("%d", &n); for(int i=0;i

注：set会自动排序、自动去重，同时注意如何取得set最后一个元素

4.总结

灵活运用 优先队列、set

5.更新日志

2022.8.6

欢迎交流、讨论、指正~ 不正确、不理解之处欢迎评论留言~

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。