洛谷 P1281 书的复制 题解
2024-09-01 07:24:11
P1281 书的复制
题目背景
大多数人的错误原因:尽可能让前面的人少抄写,如果前几个人可以不写则不写,对应的人输出0 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
【思路】
二分答案
【吐槽】
二分答案模板题目
但他的输出却很恶心人
因为要让后面的人尽量多抄的嘛
所以就要从后往前枚举
这样才能让后面的人尽量多抄
但是输出的时候却是从1-k依次输出每个人到底抄哪个范围内的书
所以很讨厌
【核心思路】
这是让抄的页数最多的人抄的最少
最大值最少
所以二分答案为什么要用就很显然了
二分抄的最多那个人抄了多少
然后从后往前枚举
check一下是不是满足在抄的最多的那个人抄的页数小于等于二分出来的这个数的情况下
可以被小于等于k个人抄完
如果能就返回真
反之返回假
这样就可以轻轻松松的二分一下一下了
【完整代码】
#include<iostream>
#include<cstdio>
using namespace std;
const int Max = 505;
int a[Max];
int xx[Max],yy[Max];
int k,m;
bool check(int x)
{
int tot = 0;
int js = 0;
for(register int i = m;i >= 1;i --)
{
if(a[i] > x)
return false;
tot += a[i];
if(tot > x)
{
if(js == k - 1)
return false;
else
tot = a[i],js ++;
}
if(js == k && i != 1)
return false;
}
return true;
}
int main()
{
int tot = 0;
cin >> m >> k;
for(register int i = 1;i <= m;++ i)
cin >> a[i],tot += a[i];
int l = 0,r = tot;
while(l < r)
{
int mid = (r + l) >> 1;
if(check(mid))
r = mid;
else
l = mid + 1;
}
yy[k] = m;
int sum = k;
int ans = 0;
a[0] = 9999999;
for(register int i = m;i >= 0;i --)
{
ans += a[i];
if(ans > l)
{
ans = a[i];
xx[k] = i + 1;
k --;
yy[k] = i;
}
}
for(register int i = 1;i <= sum;++ i)
cout << xx[i] << " " << yy[i] << endl;
return 0;
}
最新文章
- MySQL重置root密码
- C/C++预处理指令#define,#ifdef,#ifndef,#endif…
- myeclipse连接oracle步骤
- Tomcat 6.0 简介
- PAT 解题报告 1051. Pop Sequence (25)
- C++ __int64用法(转)
- Root resource classes
- PAT 1019
- 【Java基础】Integer包装类的缓冲池问题
- SQL Server 数据类型 Decimal介绍
- 对Extjs中store的多种操作
- linux下面的fd限制
- 初识Redis系列之四:.net使用Redis存储数据
- No space left on device Linux系统磁盘空间已满
- windows 通过scoop安装yarn
- L1-049. 天梯赛座位分配
- python中lambda的用法
- linux 内核移植
- SqlParameter防止SQL注入
- mongodb常用查询
热门文章
- C# vb .net实现宝丽来效果滤镜
- 接口的鉴权cookie、session和token
- catch socket error
- Spring AOP无法拦截Controller的原因
- 机智云连接esp8266--远程控制风扇转速
- php中call_user_func()与call_user_func_array()区别
- SpringBoot集成MyBatis的分页插件PageHelper--详细步骤
- 最佳移动端h5自适应rem适配方案
- tomcat将控制台输出定向到特定的文件中,并且一天一个文件
- xshell 连接出现 The remote SSH server rejected X11 forwarding request