基础算法
2022/7/25 14:27:49
本文主要是介绍基础算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
模拟:
JOG 20200807 普及模拟赛题
漫步(jog.cpp/c/pas)
(1s,512MB)
【题目描述】
有 n 组人在一条无尽的小路上漫步,每组人都有一个初始位置和速度,一组人总是会以相同的速度进行漫步,且所有人漫步的方向都相同。
因为这是一条小路,所以当一个速度更快的赶上另一组速度较慢的人时,这两组会合并成一组,而合并成的这个新组的速度与原来两组中速度较慢的那组速度相同,他们会以这个速度继续往前跑。
当然跑到最后的时候,没有任何一组会与其他组再合并。这个时候还剩下几组人?
【输入格式】
第一行两个数 n,表示初始组数。
接下一行 n 行每行两个数 d、v,表示这组的初始位置和初始速度。
数据保证所有组初始位置不同,并且读入按从小到大的顺序给出。
【输出格式】
一行一个数 ans , 表示最后还剩下几组。
【样例输入】
5
0 1
1 2
2 3
3 2
6 1
【样例输出】
2
【数据范围】
对于 30 % 的数据,n ≤ 2000。
对于 100 % 的数据,n ≤ 10^5,0 ≤ d ≤ 10^9,1 ≤ v ≤ 10^9。
模拟写法:
#include<cstdio> using namespace std; int n,v[100005],ans=1,x; int main(){ freopen("jog.in","r",stdin); freopen("jog.out","w",stdout); scanf("%d",&n); for(int i=1;i<=n;++i) scanf("%*d%d",&v[i]); x=v[n]; for(int i=n-1;i;--i) if(v[i]<=x) ++ans,x=v[i]; printf("%d",ans); return 0; }
单调队列入门:
#include <bits\stdc++.h> using namespace std; const int kMaxn = 111111; int n, a[kMaxn], top = 0; int main() { freopen("jog.in", "r", stdin); freopen("jog.out", "w", stdout); scanf("%d", &n); while (n--) { int t; scanf("%*d%d", &t); while (top && t < a[top]) {//维护一个单调不降的队列,最终队列里元素的个数就是答案 --top;//例如:1 2 3 3,说明可定都追不上 } a[++top] = t; } printf("%d\n", top); return 0; }
P3111 [USACO14DEC]Cow Jog S
有N (1 <= N <= 100,000)头奶牛在一个单人的超长跑道上慢跑,每头牛的起点位置都不同。由于是单人跑道,所有他们之间不能相互超越。当一头速度快的奶牛追上另外一头奶牛的时候,他必须降速成同等速度。我们把这些跑走同一个位置而且同等速度的牛看成一个小组。
请计算T (1 <= T <= 1,000,000,000)时间后,奶牛们将分为多少小组。
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> using namespace std; long long n,t,last[100005]; struct cow{ long long x,v; }a[100005]; int main(){ cin >> n >> t; for(int i=1;i<=n;i++){ cin >> a[i].x >> a[i].v; last[i]=a[i].x+a[i].v*t; } long long res=1, la = last[n];//long long for(int i=n-1;i>=1;i--){ if(last[i] < la){ la = last[i]; res++; } } cout<< res<<endl; return 0; }
这篇关于基础算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?
- 2024-05-09企业src漏洞挖掘-有意思的命令执行