基础算法


模拟:

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;
}

 

原创文章,作者:kirin,如若转载,请注明出处:https://blog.ytso.com/276685.html

(0)
上一篇 2022年7月24日
下一篇 2022年7月24日

相关推荐

发表回复

登录后才能评论