自动搬运

查看原文

来自洛谷，原作者为

	学无止境 冲冲冲!

搬运于2025-08-24 21:53:50，当前版本为作者最后更新于2018-02-03 00:37:20，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

$update:$ $2019.8.6$

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

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

正文:

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

贪心

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

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

$PS:$上次出门的在 $been[$ $]$ 中，我们之所以不选，是因为我们就是以been为基础选当前的兔子（因为生疏度不能太高），再贪心，将本轮选出的上次未出门且对应 $days[ ][ ]$ 与大于 $been[ ]$ 中兔子对应 $days[$ $][$ $]$ 较小的交换 $/$ 或直接赋值（因为贪心的法则，优先选天数多的加入）

( 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; 
}