题解 P3895 【[湖南集训]Hungry Rabbit】

· · 题解

update:$ $2019.8.6

之前出了一个小锅 , 导致程序会忽略一些无解的情况 , 已改正(是我太菜了)

鸣谢右侧评论区的各位大佬让我意识到的我的问题. orz

正文:

既然你看到了这里，先猜猜解法是什么？（不否认其他解法的存在）

贪心

贪心 max 级别难度的题目（不明白为什么6000ms，贪心只用了500多ms就 AC 了）。

（1） 每轮判断根据 （3），只要能出门（对应 days[ ][ ] 大于零且上次没出门）就加入序列 being[ ]

( 2 ) 我们要让哪些兔子去第i轮，因为有l（生疏度）这个玩意，所以优先选i-1去过的（第一轮特殊处理）

( 3 ) 其次我们定义一个二维数组 days[ ][ ] ,来存每天每只兔子从当天开始可以连续出去觅食几天而不死掉，我们优先选对应天开始出去天数多的（因为之后不能生疏度过低，要保证兔子可以连续出门），所以要排序，这里我们将天数多的往前排。

（4） 但我们会发现一个问题，从 i-1 的决策中筛选第i天会有一个尴尬情况——有的兔子出不了门，那么我们就以 ( 3 ) 的标准，从 i-1 天出门兔子序列后往前判断（排过序了，靠后兔子的可连续出门天数少，最可能会死），此时就用 ( 1 ) 中 PS 说的方法，替换值，但是注意，不止替换会死的，还替换天数少的（在生疏度范围内）

什么时候输出 -1 呢？在没有 been 的第一天，我们判兔子够不够，其余判断时就看有没有 0 在里面（有就代表选不出来）

可能大部分人看到这里还是蒙的，可以先看代码，多花点心思想想，结合上面的说明慢慢就理解了。

Code：

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
int n,m,k,l,been[810],being[810],isit[810],days[810][810],ans[810][810],q;//days存从当天开始天兔子可持续觅食的天数 
char wolf[810][810];

bool cmp(int a,int b)
{
    return days[q][a]>days[q][b];//排序规则：将天数多的往前放，q是全局变量 
}

inline char _getchar()
{
    register char c=getchar();
    while(!isdigit(c))
        c=getchar();
    return c;
}

int main()
{
    scanf("%d%d%d%d",&n,&m,&k,&l);
    for(register int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            wolf[j][i]=_getchar(); //读入狼捕杀兔子的表，注意是char！不能用int，因为中间没有空格 
    for(register int i=m;i>0;i--)
        for(register int j=1;j<=n;j++)
            if(wolf[i][j]=='1')   
                days[i][j]=days[i+1][j]+1;
            else    
                days[i][j]=0;//处理出每天对应兔子从对应天开始最大连续出门天数 
    for(q=1;q<=m;q++)//m天 
    {
        register int u=0;//u代表选出来的上次没出门的且这次可以出门的兔子个数 
        for(register int i=1;i<=n;i++)
            if(days[q][i]&&!isit[i])
                being[++u]=i; //being存上次没出门的且这次可以出门的兔子序列 
        sort(being+1,being+1+u,cmp);//将其排序，便于贪心 
        if(q==1)//在第一天，没有been，特判 
        {
            if(u<k)//兔子不够就输出-1，return 0; 
            {
                printf("-1\n");
                return 0;
            }
        }
        else//除第一天外 
        {
            register int i;
            sort(been+1,been+1+k,cmp);//been因为值被操作了，所以每次要排序 
            for(i=1;i<=u&&i<=l;i++)//既要满足生疏度，也要满足在下标范围内（小于等于u） 
                if(days[q][being[i]]>days[q][been[k-i+1]])//在生疏度范围内，从being中由大致小判断能不能替换been中天数少的兔子————贪心法 
                    been[k-i+1]=being[i];//能就换 
            if(i!=k+1&&!days[q][been[k-i+1]])//最后（如果换了）换的是been[k-i+1]，它非零整个been序列也非零，但要加上i!=k+1，应对 l==k或u==k的情况，这时k-i+1=0，那么瞬间爆炸（忽略这一点会WA第一个点） 
            {
                printf("-1\n");
                return 0;
            }
            swap(been,being);//要存答案了，交换后答案在being （交换的原因：下面还要换（除q==1的特判）） 
        }
        memset(isit,0,sizeof(isit));//isit存上次去的兔子 
        for(register int i=1;i<=k;i++)
            isit[being[i]]=1,ans[q][i]=being[i];//这次去了，isit对应为1，并存答案 
        swap(been,being); //每天结束后当前的 being就是下一天的been 
    }
    for(register int i=1;i<=m;i++)//输出不解释 
    {
        for(register int j=1;j<=k;j++)
            printf("%d ",ans[i][j]);
        printf("\n");
    }
    return 0; 
}