HNU软件能力实训2-21. 新型冠状病毒（COVID19）传播

写在前面

你好！欢迎来到我的博客，希望我的思路能够帮到你！

问题描述

防控新冠病毒，必须时刻引起大家的足够重视，特别是人员集中活动场所，保持好社交距离。

然而，在大洋彼岸的 M 国，人们对COVID19并未引起足够重视，他们的领导人川建国同志甚至对居家隔离、戴口罩以及保持社交距离等措施非常不屑，该国疫情已经完全失控。

在一个风景秀丽的小镇，一天早上，有 N 名晨跑爱好者（编号 1 ～ N ）沿着优雅的江边景观道朝同一方向进行晨跑，第 i 名跑者从位置 Si 处起跑， 且其速度为 Vi。换句话说，对所有的实数 t ≥ 0，在时刻 t 时第 i 名跑者的位置为 Si + Vi ·t。

很不幸的是，其中一名跑者在 t = 0 的时刻感染了病毒，且是无症状感染者，这种病毒只会在同一时刻处在同一位置的跑者之间传播，新感染了病毒的跑者也会感染其他人，很显然，等待足够长的时间，那么病毒会感染一些特定的跑者。

事后发现其中有一名跑者感染了新冠病毒，如果此人就是在 t = 0 时刻的那名感染者，那么，在 N 名晨跑爱好者中会有多少人感染新冠病毒？

输入形式

输入包含三行：

• 第一行包含为两个整数 N 和 K，分别表示运动员的人数以及开始时感染了病毒的跑者编号。

• 第二行包含 N 个正整数 S1、S2、…、SN，用空格隔开，分别表示跑者的起始位置。

• 第三行包含 N 个正整数 V1、V2、…、VN，用空格隔开，分别表示跑者的速度。

输出形式

输出为一个整数，表示最终被感染人数。

样例输入

6 3
3 9 8 5 7 5
6 6 5 4 6 3

样例输出

3

数据范围

对于50%的评测用例，0< K ≤ N ≤10²

对于70%的评测用例，0< K ≤ N ≤10⁴

对于90%的评测用例，0< K ≤ N ≤10⁶

对于100%的评测用例，0< K ≤ N ≤10⁷

解题思路

不得不说，这是训练二中最难的一道题，也是一道追及问题，而作为理科生的我们，肯定都知道物理老师曾经说过的 x-t 图法，但是这道题并不是用 x-t 图法做，而是用于理解题意。

话不多说，上图！

显然，根据高中物理，①-⑥中，有③和④最终会被感染。但是因为找出所有感染者的思路较难，所以我们反向寻找，找到安全的人的数目。

而安全的人有什么特点呢？

我们将安全的人分为两个部分：一部分人初始位置小于零号感染者；另一部分人初始位置大于零号感染者。

初始位置小于零号感染者的人要想不被感染，其速度只能小于等于右边所有人的最小速度。因为我们将零号感染者看做在右边。右边速度最小的那个人一定会被零号感染者感染。而左边人的速度要是大于这个最小速度，那么也会被感染。

所以初始位置大于零号感染者的人要想不被感染，其速度只能大于等于左边所有人的最大速度。

所以我们以零号感染者作为分界后，找出左边的最大速度，右边的最小速度。

遍历右边时，如果速度大于该速度且位置大于零号感染者的位置，我们将计数器+1。

再遍历左边，遍历时如果速度小于右边的最小速度且位置小于零号感染者的位置，将计数器+1。

最后输出总人数减去安全人数就是答案。

AC代码

#include<iostream>
#include<algorithm>
using namespace std;

struct people
{
    int num;//储存输入的顺序，方便在遍历时找到零号感染者
    int pos;//位置
    int v;//速度
};

bool cmp(const people &l,const people &r)
{
    if(l.pos==r.pos)
    {
        return l.v>r.v;
    }
    return l.pos<r.pos;
}

const int N=10000500;
//发现如果N开成10000010会爆内存
//所以N开大点
people p[N];

int main()
{
    int n,s;
    cin>>n>>s;
    for(int i=0;i<n;i++) cin>>p[i].pos;
    for(int i=0;i<n;i++)
    {
        p[i].num=i+1;//初始化编号
        cin>>p[i].v;
    }
    sort(p,p+n,cmp);//排序
    int lmaxv=-1;
    int mid;//存储零号感染者的位置
    for(mid=0;mid<n;mid++)
    {
        if(p[mid].v>lmaxv) lmaxv=p[mid].v;
        //寻找左边速度最大值
        if(p[mid].num==s) break;
        //如果当前选手是零号感染者，退出循环
    }
    int safe=0;//储存未感染人数
    int rminv=1000000;//初始化
    for(int i=mid;i<n;i++)
    {
        if(p[i].v>=lmaxv&&p[i].pos>p[mid].pos)
            safe++;
        //如果右侧选手速度大于左边的最大速度
        //且右边选手的位置大于零号感染者的位置
        if(p[i].v<rminv) rminv=p[i].v;
        //找到右边速度最小值
    }
    for(int i=0;i<mid;i++)
    {
        if(p[i].v<=rminv&&p[i].pos<p[mid].pos)
            safe++;
        //如果左边选手速度小于右边的最小速度
        //且左边选手的位置小于零号感染者的位置
    }
    cout<<n-safe<<endl;
    //输出总人数减去安全人数
    system("pause");
    return 0;
}

写在最后

如果代码有任何问题，欢迎评论或者私信斧正。如果内容对对你有启发，不妨点个赞吧