练习：C++模拟——病毒传染

练习：C++模拟——病毒传染 【问题描述】

在M国一个风景秀丽的小镇，一天早上，有 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 ≤

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

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

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

【解决办法】

首先我们要耐心读题。

读完题后，思考一下：在什么情况下跑者一定会被感染？

 我们可以画s-t图来分析。

 在感染者之后出发，比感染者快的，一定被感染；

在感染者之前出发，比感染者慢的，一定被感染；

还有吗？

上述感染者我们称之为第一批感染者。在跑步的过程中，他们会去感染别的未感染的跑者。

起始点在感染者之上的，暂且称为“上层”

起始点在感染者之下的，暂且称为”下层“

好了，就这四种情况。（麻了，现在说得轻松，考试时想了半天。）

上代码。

#include 
#include
#include
using namespace std;
class person
{public:
    int x0;
    int v;
};
bool faster(person p1,person p2)
{
    return p1.v>p2.v;
}
bool slower(person p1,person p2)
{
    return p1.v>n;
    person *a=new person [n];
    int k;cin>>k;

    for(int i=0;i>a[i].x0;
    for(int i=0;i>a[i].v;
    vector fronCovid;
    vector bihiCovid;
    vector fronno;
    vector bihino;
    int sum=0;
    for(int i=0;ia[k-1].x0)
        {   if(a[i].va[k-1].v)
                {bihiCovid.push_back(a[i]);sum++;}
                else
                    bihino.push_back(a[i]);
            }
    }
    sort(bihiCovid.begin(),bihiCovid.end(),faster);
    sort(fronCovid.begin(),fronCovid.end(),slower);
    for(unsigned i=0;ifronCovid[0].v)
            {sum++;}
    }
  cout< 
测试效果：
 
 
 有一个数据没有通过。我怀疑是0< K ≤ N ≤的那一组。因为数据太大了。
 
 
 
 
 
 
 
另外，我们可以尝试寻找一定不会被感染的跑者。
 
通过之前的分析，我们可以知道，一定不会被感染的只有两种情况：
 
1.上层跑者的速度比初始感染者和下层所有跑者速度都快；
 
2.下层跑者的速度比初始感染者和上层所有跑者速度都慢；
 
这样也是可以做出来的。
 
然而怎么优化使其通过所有测试数据，还是一个有待解决的问题。
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5699256.html