题解 P1413 【坚果保龄球】

CPT_Penner · 2019-05-28 21:06:12 · 题解

我刚开始做这道题，想着是模拟，检查到当zombie走到最后一格的时候，判断一下此时这一行有没有其他的zombie，如果有，那么就杀死它。

后来换了一个思路，结构体中的p储存行数，t储存出现时间。

将所有的时间按升序排序，如果当一个zombie在最后一个，那么这一行中离这个zombie距离小于60的zombie都会被杀死，在我的程序中用p（行数）来判断。设zombie为A且此时A正好在这一行的最左侧，如果一个zombie的行数与A行数相同且当A在最左侧时这个zombie已经出现，那么就将这个zombie的行数设定为0（意味着已经死了），这样从头到尾扫一次。

找到A后，我已开始忘记了往后扫的时候要设置不超过僵尸总数，导致了疯狂RE

#include<bits/stdc++.h>
using namespace std;
struct ppp{//这里定义了一个储存行数和时间的结构体
    int p;
    int t;
}a[20001];
int n,sum;
int cmp(ppp x,ppp y)//这是sort排序用的
{
    return x.t<y.t;//根据时间升序排序
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
    cin>>a[i].p>>a[i].t;
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        if(a[i].p!=0)//这里如果p==0，则代表已经被坚果打到了，也就是不等于0时放一个坚果
        {
            sum++;//多一个
            for(int j=i+1;a[j].t-a[i].t<60&&j<=n;j++)//从这个开始循环，如果某一只zombie在同一行且离这只zombie小于60格的话，就把他碾死
            if(a[j].p==a[i].p)//判断是否在同一行
            a[j].p=0;//把可爱的小zombie杀死，将它移除
        }
    }
    cout<<sum;
    return 0;
}