描述
题解
给定n个数,分为m个区间,保证m个区间的元素数目都是一样并且尽可能多,剩余的无法均分的则舍去,忽略。
网上见到很多人这道题都是二分+RMQ写得,但是,实际上是有问题的,因为并不是段数越多,值就越大,比如说:3 4 55 55 2 3
,如果分为三段,结果4+55+3=62
,而如果分为两段,55+55=110
了,所以说这道题需要枚举+RMQ,可是这里如果不剪枝会特别悬,很有可能TLE
,这里说到一个优化就是如果分为x
段得到的长度len
等于分成x-1
段得到的长度len_
,那么只要把前一次的结果加上这一次第x
段的最大值即可。
代码
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
/* * 求最大值,数组下标从1开始。 * 求最小值,或者最大最小值下标,或者数组从0开始对应修改即可。 */
const int MAXN = 2e5 + 10;
int n, k;
int dp[MAXN][20];
int mm[MAXN];
// 初始化RMQ,b数组下标从1开始,b数组是区间元素序列
void initRMQ(int n, int b[])
{
mm[0] = -1;
for (int i = 1; i <= n; i++)
{
mm[i] = ((i & (i - 1)) == 0) ? mm[i - 1] + 1 : mm[i - 1];
dp[i][0] = b[i];
}
for (int j = 1; j <= mm[n]; j++)
{
for (int i = 1; i + (1 << j) - 1 <= n; i++)
{
dp[i][j] = max(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
}
}
}
// 查询最大值
int rmq(int x, int y)
{
int k = mm[y - x + 1];
return max(dp[x][k], dp[y - (1 << k) + 1][k]);
}
int solve()
{
int prev = -1, sum = 0, j = 1, left, right;
for (int i = 1; i <= n; i++)
{
int l = n / i;
if (prev != l)
{
j = 1;
sum = 0;
}
while (j <= i)
{
left = (j - 1) * l + 1;
right = j * l;
sum += rmq(left, right);
if (sum > k)
{
return i;
}
j++;
}
prev = l;
}
return -1;
}
int b[MAXN];
int main()
{
while (scanf("%d%d", &n, &k))
{
if (n == -1 && k == -1)
{
break;
}
for (int i = 1; i <= n; i++)
{
scanf("%d", b + i);
}
initRMQ(n, b);
printf("%d\n",solve());
}
return 0;
}