csu 1976: 搬运工小明
2024-09-06 09:43:46
1976: 搬运工小明
Submit Page Summary Time Limit: 2 Sec Memory Limit: 128 Mb Submitted: 94 Solved: 27
Description
作为老人的小明非常忧伤,因为他马上要被流放到本部去了,住进全左家垅最有历史感的11舍真是一件非常荣幸的事情。
搬行李是个体力活,小明发现自己的行李太多啦,所以他决定去买很多个袋子来装走。到了超市的小明发现,不同大小的袋子居然价格一样???虽然买最大的自然最赚,但是小明是名远近闻名的环保人士,他觉得袋子只要能装下他的行李就够了,并且为了不麻烦收银的小姐姐(⊙o⊙)…,他也只会购买同一种大小的袋子。因此他希望在能装下所有行李的前提下,袋子越小越好。同时为了避免弄乱行李,小明希望同一个袋子装的是位置连续相邻的行李。
小明摸了摸口袋发现自己带的钱最多能买N个袋子,数学特别差的他不知道到底该买多大的才合适,所以想靠你来解决这个问题了。
Input
第一行为一个数字T(T<=10)表示数据组数
第二行为两个数字N(N <= 10^5)和 M(M <= 10^5)表示袋子个数和小明的行李个数
第三行为M个数字,第i个数字a[i]表示小明的第i个行李体积为a[i](0<a[i] <= 10^9)
Output
输出一行表示袋子的最小体积(整数)
Sample Input
1
3 3
1 1 1
Sample Output
1
Hint
袋子不能装下体积大于其容积的物品
多个物品满足体积之和小于等于一个袋子的容积,就能被装进
Source
2017年8月月赛
Author
卢铭威
题解:
二分袋子的体积就好了
、
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
long long int a[];
int n,m;
bool jug(long long int x)
{
int k=;
long long int sum=;
for(int i=;i<=m;++i)
{
if(a[i]+sum<=x)
{
sum+=a[i];
}
else
{
sum=a[i];
k++;
}
}
if(k>n)return false;
return true;
}
int main()
{
int T; scanf("%d",&T);
while(T--)
{
long long int r=;
long long int l=; long long int mid;
scanf("%d %d",&n,&m);
for(int i=; i<=m; i++)
{
scanf("%lld",&a[i]);
l=max(l,a[i]);
r+=a[i];
} while(l<=r)
{
mid=(l+r)>>;
if(jug(mid))
r=mid-;
else
l=mid+;
}
printf("%lld\n",mid);
} return ;
}
最新文章
- 项目编码规范(Ali)
- 用Kotlin开发Android应用(III):扩展函数和默认值
- [LeetCode] Ugly Number
- netbean快捷键
- android动态调试samli代码(转)
- memory_limit的一个bug | 风雪之隅
- AGS API for JavaScript 图表上地图
- bzoj3261 可持久化trie
- java.lang.NullPointerException: Attempt to invoke virtual method &#39;void 、Handler.removeMessages(int)&#39; on a null object reference
- 在MVC中如何愉快使用Ajax
- 基于visual Studio2013解决算法导论之021单向循环链表
- URAL 1180. Stone Game (博弈 + 规律)
- C++多线程二
- 注销/etc/passwd带来的系统登陆不上
- 开源博客系统使用springmvc
- win10下正确使用Sublime Text搭建python调试环境
- laravel 服务提供者介绍和使用
- C语言代码复习笔记:第二章
- vuejs全局api概念
- WPF选择文件、文件夹和另存为对话框