P1413 坚果保龄球 题解

hensier · 2020-02-22 13:00:51 · 题解

这道题可以用sort辅助进行判断。在输入n以后，我们可以在[1,n]区间进行输入，对于每一个i输入两个参数并操作。

该部分代码如下：（备注：i为循环使用的变量，k、l为每一个i所输入的两个参数，a[]为保存每一排僵尸数量的数组，z[][]这个二维数组的第一个下标表示排数，第二个下标表示数量，而z[][]这个数值则表示僵尸所侵入的时间）

for(i=1;i<=n;i++)
{
    scanf("%d%d",&k,&l);
    a[k]++;
    z[k][a[k]]=l;
}

由于输入的时间不一定按先后排序，因此我们要用sort进行处理。具体方式是：（备注：由于sort排序用的是指针，因此对于二维数组同样适用）

for(i=1;i<7;i++)std::sort(z[i]+1,z[i]+a[i]+1);

我们根据分析，可以发现：假若两个相邻的僵尸侵入时间小于60，则可以用同一个坚果保龄球消灭。因此我们可以令初始时间等于每一列第一个僵尸进入的时间，然后每一次时间大于等于60就替换并让计数器加1。

代码核心部分：

for(i=1;i<7;i++)
{
    if(!a[i])continue;//如果没有僵尸就直接进入下一层循环
    m++;//如果现在是第一个僵尸就让计数器加1（例：如果该列只有1个僵尸，也需要1个坚果，所以如果该列有僵尸，则初始要加1）
    f=0;//标记时间是否已经改变过
    if(!f)
    {
        s=z[i][1];//将时间设定
        f=1;
    }
    for(j=2;j<=a[i];j++)
    {
        if(z[i][j]-s>=60)//判断时间差
        {
            s=z[i][j];//替换时间
            m++;//坚果数量加1
            f=0;
        }
    }
}

核心部分处理完以后，直接输出m即可。