2023 百度之星（夏日漫步 + 跑步问题）

2023百度之星 夏日漫步 + 跑步问题

前言

继续为大家带来百度之星的题目以及详解，都是AC的，大家可以放心食用。往期的博客可以看这里
2023百度之星 题目详解 公园+糖果促销
喜欢的小伙伴可以点个关注啦！！！

夏日漫步问题

问题详情

夏日夜晚，小度看着庭院中长长的走廊，萌发出想要在上面散步的欲望，小度注意到月光透过树荫落在地砖上，并且由于树荫的遮蔽度不通，所以月光的亮度不同，为了直观地看到每个格子的亮度，小度用了一些自然数来表示它们的亮度。亮度越高则数字越大，亮度相同的数字相同。

走廊是只有一行地砖的直走廊。上面一共有 n 个格子，每个格子都被小度给予了一个数字 a i 来表示它的亮度。
小度现在站在 1 号格子，想要去到 n 号格子。小度可以正向或反向移动到相邻的子，每次需要花费 1 的体力。
同时小度还有瞬移的能力，其可以花费 1 的体力来瞬移到与当前格子亮度相同的格子上。而且由于小度视野有限，只能瞬移到在当前格子后的第一次亮度相同的格子上。这也意味着不能反向瞬移。

小度想知道，到达 n 号格子需要花费的最小体力是多少。以此制定一个最优秀的散步方案。
输入格式：
第一行一个整数 n ，表示走廊上一共有 n 个格子。

1≤n≤2∗10^5;
0<=ai<=1*10^6;

第二行 n 个整数，为自然数 ai​ 表示第 i 号格子的亮度。
输出格式：
一行，一个整数 cost表示花费的最小体力。

题目详解

对于那些相邻的点，我们只需要把它们放进邻接表就行，对那些亮度相同的点，我们可以按照亮度排序，这样那些亮度相同的点就在一起了。

#include
#include
#include
#include
using namespace std;
const int N =2e5 + 7,M=3*N;
typedef pair<int,int> PII;
PII a[N];
bool st[N];
int dist[N],e[M],ne[M],h[N],idx,n;
void add(int a,int b){
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
int bfs(){
    memset(dist,-1,sizeof dist);
    dist[1]=0;
    queue<int> q;
    q.push(1);
    st[1]=true;
    while(!q.empty()){
        auto t=q.front();
        q.pop();
        for(int i=h[t];i!=-1;i=ne[i]){
            int j=e[i];
            if(!st[j]){
                dist[j]=dist[t]+1;
                q.push(j);
                st[j]=true;

            }
        }
    }
    return dist[n];
}
int main(){
    cin>>n;
    memset(h,-1,sizeof h);
    for(int i=1;i<=n;i++){
        int x;cin>>x;
        a[i]={x,i};
    }
    sort(a+1,a+n+1);
    // for(int i=1;i<=n;i++){
    //     cout<<a[i].first<<' '<<a[i].second<<endl;
    // }
    for(int i=1;i<n;i++){
        add(i,i+1);
        add(i+1,i);
    }
    for(int i=1;i<n;i++){
        if(a[i].first==a[i+1].first){
            add(a[i].second,a[i+1].second);
        }
    }
    cout<<bfs()<<endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

跑步问题

题目描述

小度每天早上要和小猫一起跑步。小猫的位置数值越小表示越在后面，速度越小表示越慢，它们都向一个方向跑。
小猫比较喜欢一起跑，所以当速度更快的小猫遇见速度慢的小猫时，它就会放慢速度，变成一组一起跑。注意，初始位置相同的小猫直接组成一组。
请问最终不再有追赶上的情况时，最多一组有多少只小猫？
输入格式：
第一行输入的是整数 n，
接下来的n行分别包含小猫的初始位置 p 和速度 v ， 1<= p,v<=1*10^8
输出格式：
一行，一个数字，表示最多有多少小猫在一组。
输入：

5
6 1
1 1
3 2
1 2
2 3
1
2
3
4
5
6

输出：

3
1

样例解释：位置速度为（3,2），（2,3）的小猫会追上（6,1）的小猫，而位置速度为（1,2）的小猫则会和（1,1）一起，所以最多三只小猫一组。

题目详解

排好序之后，记得从后往前遍历

#include 

using namespace std;
const int N =1e5 + 7;
int cnt[N];
struct Cat{
    int p,v;
    bool operator <(const Cat&W) const{
        if(p==W.p) return v<W.v;
        else return p<W.p;
    }
}cat[N];
int main( )
{
    int n;cin>>n;
    for(int i=1;i<=n;i++){
        int x,y;cin>>x>>y;
        cat[i]={x,y};
    }
    sort(cat+1,cat+1+n);
    
    for(int i=1;i<n;i++){
        if(cat[i].p==cat[i+1].p){
            cat[i+1].v=cat[i].v;
        }
    }
    int res=0,index=n,cnt=1;
    while(index-cnt>0){
        
        if((cat[index].p!=cat[index-cnt].p&&cat[index].v<cat[index-cnt].v)||cat[index].p==cat[index-cnt].p) cnt++;
        else index-=cnt,cnt=1;
        res=max(res,cnt);
    }
    cout<<res<<endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35