自动搬运

查看原文

来自洛谷，原作者为

	s_ShotღMaki 不要下这么应时的雨啊

搬运于2025-08-24 21:43:01，当前版本为作者最后更新于2019-03-06 22:59:32，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

看有大佬在讨论区里求助，我做了一下这个题

这题的话首先我们读题，看看是考什么的！

(读着读着题目 诶诶诶！！！这题我好像做过诶！

P1182是你，是你！！！就是你！

于是复制那题提交过的代码就秒掉了

咳咳，进入正题，本题是一个

二分+贪心

其实非常好做，类似一个二分的板子题，我看了一下题解，大家都是用

前缀和

但那样有点浪费空间呢！所以我们check函数要这个样子，每次都全扫一遍，加上跟tot比一比，如果小于就加上，最后比一比num和m就好了，如果小，那就说明是合法的！

但l一定要取所有数中最大的哦！

贴完整代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

inline int read ()
{
    int f = 1, x = 0;
	char ch;
    do {ch = getchar (); if (ch== '-') f = -1;} while (ch < '0' || ch > '9');
    do {x = x * 10 + ch - '0'; ch = getchar ();} while (ch >= '0' && ch <= '9');
    return f * x;
}

int n, m;
int a[100005];
int l, r, mid;
int ans;

inline bool check (int hehe)
{
	int tot = 0, num = 0;
	for (int i = 1; i <= n; i ++)
	{
		if (tot + a[i] <= hehe) tot += a[i]; //如果装得下就加上
		else tot = a[i], num ++;//装不下就num++
	}
	return num >= m;
}

int main ()
{
	n = read (); m = read ();
	for (int i = 1; i <= n; i ++)
	{
		a[i] = read ();
		l = max (a[i], l);
		r += a[i];
	}
	while (l <= r) //二分板子
	{
		mid = l + r >> 1;
		if (check (mid)) l = mid + 1, ans = l;
		else r = mid - 1, ans = l;
	}
	printf ("%d\n", ans);
	return 0;
}

可以说是很快的辣！而且空间用的也少！