题目:
奶牛们又出去锻炼蹄子去了!
有 N 头奶牛在无限长的单行道上慢跑。
每头奶牛在跑道上开始奔跑的位置都不相同,一些奶牛的奔跑速度也可能不同。
由于跑道是单行道,十分狭窄,奶牛们无法相互超越。
当一头速度很快的牛追上另一头牛时,她必须减速至与另一头牛速度相同以免发生碰撞,并成为同一跑步小组的一员。
最终,再也没有奶牛会撞到(追上)其他奶牛了。
约翰想知道在这种情况下,会剩下多少个跑步小组。
输入格式:
第一行包含整数 N.
接下来 N 行,每行包含一头奶牛的初始位置和跑步速度。
所有奶牛的初始位置各不相同,且是按照递增顺序给出的。
输出格式:
输出一个整数,表示最终剩下的小组数量。
数据范围:
1≤N≤105,
初始位置范围 [0,109],
跑步速度范围 [1,109]
输入样例:
5
0 1
1 2
2 3
3 2
6 1
输出样例:
2
**分析:刚开始一看有点难理解,但是我看了一位大佬的的代码,瞬间就理解了。(这个位置就没有用了)
思路是这样的:x升序,不记录,无所谓,只是代表先后关系;
你想一想,假如最后一个牛慢到离谱(接近0),所有牛都会追上他,是不是只有一组队; 所以一个牛比前面的牛慢,就会合并前面的牛;
这位大佬的思路是:从最后面判断,如果前一项比后一项大,就替换前一项的值,如果不大,就计数+1;
刚开始我还不是很懂但是例子带加进去之后,就马上理解了;**
源码:
include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int main()
{
int n,a,b[N]; cin >> n; for (int i = 0; i < n; i ++ ) { cin >> a>>b[i]; } int arr=1; for(int i=n-1;i>0;i--) { if(b[i]<b[i-1]) { b[i-1]=b[i]; } else{ ++arr; } } cout << arr<<endl; return 0;
}