【基础练习】【二分】洛谷1281 书的复制题解

朱雀 2022-08-09 06:27 171阅读 0赞

## 现在要把m本有顺序的书分给k给人复制（抄写），每一个人的抄写速度都一样，一本书不允许给两个（或以上）的人抄写，分给每一个人的书，必须是连续的，比如不能把第一、第三、第四本书给同一个人抄写。 ##

现在请你设计一种方案，使得复制时间最短。复制时间为抄写页数最多的人用去的时间。

输入格式：

第一行两个整数m，k；（k≤m≤500）  
第二行m个整数，第i个整数表示第i本书的页数。

输出格式：

共k行，每行两个整数，第i行表示第i个人抄写的书的起始编号和终止编号。k行的起始编号应该从小到大排列，如果有多解，则尽可能让前面的人少抄写。

输入样例\#1：

9 3
    1 2 3 4 5 6 7 8 9

输出样例\#1：

1 5
    6 7
    8 9

洛谷的格式早已无力吐槽

显然是二分裸，codevs有三个版本，一会儿也要写一下

只是要求输出每个人抄的书

结果这么一个简单的代码出了很多低级错误，主要是思路上和细节上的。比如cnt最后忘了--，比如开始写的边检查是否can边存储每个人抄哪几本书，忽略了正解会被二分其他尝试覆盖···

具体看代码吧

//Âå¹È1281 ÊéµÄ¸´ÖÆ ¶þ·Ö
    //copyright by ametake
    #include
       
        
    #include
        
         
    #include
         
           
    using namespace std;
    
    const int maxn=500+10;
    int m,k;
    int a[maxn],b[maxn][3];
    
    bool can(int x)
    {
    	bool ok=false;
    	int now=x,cnt=1;
    	for (int i=k;i>=1;i--)
    	{
    		if (ok) break;
    		while (now-a[cnt]>=0)
    		{
    			now-=a[cnt];
    			cnt++;
    			if (cnt>m)
    			{
    				ok=true;
    				break;
    			} 
    		}  
    		now=x;
    	}
    	cnt--;
    	if (cnt>=m||ok) return true;
    	else return false;
    }
    
    int main()
    {
    	freopen("1.txt","r",stdin);
    	scanf("%d%d",&m,&k);
    	int l=1,r=0;
    	for (int i=1;i<=m;i++)
    	{
    		scanf("%d",&a[i]);
    		r+=a[i];
    	}
    	while (l
          
           =1;i--)
    	{
    		b[i][2]=cnt;
    		while (now-a[cnt]>=0)
    		{
    			now-=a[cnt];
    			cnt--;
    			if (cnt==0)
    			{
    				break;
    			}
    		}
    		b[i][1]=cnt+1;
    		now=l;
    	}
    	for (int i=1;i<=k;i++)
    	{
    		printf("%d %d\n",b[i][1],b[i][2]);
    	}
    	return 0;
    }

——稻花香里说丰年，听取蛙声一片