[题解] [CF 1250J] The Parade

题面

题目大意:

给定一个 \(n\) , 所有军人的数量均在 \([1, n]\)

给定 \(a_i\) 代表高度为 \(i\) 的军人的个数

你要将这些军人分成 \(k\) 行, 满足下面两个条件

每行人数相等
同一行任意两个军人的高度差的绝对值不超过 1

问你最多能够选多少个军人分成 \(k\) 行

题解

题目满足单调性, 可以二分

我们二分一个 \(mid\) 表示每一行有 \(mid\) 个军人

不难证得首先将高度相等的分成一行, 再分高度不相等的是最优的

简要证明 : 可将不是上述方案的方案调整为是上述方案的方案, 结果不会更差

那么现在我们就是要看怎么分是最优的

我们将高度为 \(i + 1\) 的并到 \(i\) 上去等价于把 \(i\) 的并到 \(i + 1\) 上去

假如说 \(a_{i + 1} >= a_i \% mid\) , 我们就可以将 \(a_{i + 1}\) 减去 \(a_i \% mod\) , 再将 \(ans\) 加一

正确性:

首先如果不用 \(a_i\) 剩下的, 和这部分剩下的配对的 \(a_{i + 1}\) 肯定是要跟自己或者 \(a_{i + 2}\) 配对的

也就是说这一部分肯定是要用的, 如果用在自己和后面身上, 可能会导致后面的无法配对

也就是说

这一部分总会配对, 跟前面配对的不会对后面造成影响, 因为后面的总数没变

跟后面的配对可能会对后面的答案造成影响, 因为总数变了

由此可见这样配对不会更差

Code

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdio>

typedef long long ll;

const int N = 30005;

using namespace std;

int T, n;

ll k, a[N], b[N], ans, sum; 

template < typename T >

inline T read()

{

	T x = 0, w = 1; char c = getchar();

	while(c < '0' || c > '9') { if(c == '-') w = -1; c = getchar(); }

	while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();

	return x * w;

}

bool check(ll x)

{

	ll res = 0; b[1] = a[1];

	for(int i = 1; i <= n; i++)

	{

		res += b[i] / x;

		b[i + 1] = a[i + 1];

		if(b[i + 1] >= x - (b[i] % x))

			b[i + 1] -= x - (b[i] % x), res++;

	}

	return res >= k;

}

int main()

{

	T = read <int> ();

	while(T--)

	{

		ans = sum = 0; n = read <int> (), k = read <ll> ();

		for(int i = 1; i <= n; i++)

			sum += (a[i] = read <ll> ());

		a[n + 1] = 0;

		ll l = 1, r = sum;

		while(l <= r)

		{

			ll mid = (l + r) >> 1;

			if(check(mid)) ans = mid, l = mid + 1;

			else r = mid - 1;

		}

		printf("%lld\n", 1ll * ans * k);

	}

	return 0;

}

巴特西

[题解] [CF 1250J] The Parade

题面

题解

Code

最新文章

热门文章