题解 P1413 【坚果保龄球】

x义x · 2018-04-01 10:43:02 · 题解

一道很简单的贪心模拟题~

想必大家已经想出贪心思路了：只有当一个zombie抵达第一列，我们才会不得不放坚果。很显然，这肯定是最佳方案。

具体实现思路是对每一行单独处理，对于每一只抵达第一行的zombie，用坚果杀死它，顺便杀死所有当前也在这行的zombie。

到底怎么写呢？请看代码。

#include<bits/stdc++.h>
using namespace std;

int t[7][2001];
int n,ans;

int main()
{
    cin>>n;
    int j[7];for(int i=1;i<=6;i++) j[i]=0;  //喜闻乐见的读入环节~ 

    for(int i=1;i<=n;i++)  //这里用time[i][j]表示第i行的第j只zombie的抵达时间 
    {
        int t1,t2;cin>>t1>>t2;
        t[t1][++j[t1]]=t2+60;
    }

    for(int i=1;i<=6;i++)
        sort(t[i]+1,t[i]+1+j[i]);
    /*
    for(int i=1;i<=5;i++)
    {
        for(int k=1;k<=j[i];k++)
            cout<<t[i][k]<<' ';
        cout<<endl;
    }
    */  //调试时用的 
    for(int i=1;i<=6;i++) //对每一行分别处理
    {
        int x=1; //从这一行的第一只zombie开始碾压 
        while(x<=j[i])
        {
            ans++;
            int x1=x; 
            while(t[i][x1]<t[i][x]+60) x1++;
            //碾压所有同时在这一行的zombies！!注意<不能打成<=,否则样例都过不了 
            x=x1;
        }
     }

    cout<<ans; 
 } 

总之，其实这题真的不难，不过在一些细节方面上要注意。

比如：

• 这道题的行数有6行而不是真正的pvz里的5行，我因为找不出这个错误还专门在讨论里发了个帖子……蠢啊
• 样例中zombie出现的次序是排序好的，但数据不是，所以要sort一下。如果刚学快排可以拿这题练练手。
• 注释中警告的那处。我们要碾压的最前面的zombie是在第1行，但第1+60=61行的那只zombie还没走上草地，所以那里应该是<而非<=。

感谢浏览！如果你认为这篇题解的讲解还不错的话，请您为这篇题解点赞哦~