CF760B

你好。

题面

分

m

个物品给排成一排的

n

人，求第

k

个人可以拿到的最大物品数，要求相邻的人物品数相差不超过

1

，且每个人都有物品。

题解

二分第

k

个人可以拿到的物品数

x

。

若第

k

个人拿到

x

个物品，则可以构造出一种方案，使得这一排人拿到的物品数最小。

如果第

i

个人拿到

j

个物品，那么第

i-1

和

i+1

人可以拿到

j-1

或

j

或

j+1

个物品。

由此我们可以这样构造：第

k

个人拿到的最多，然后区间

[k,n]

从

k

到

n

递减，区间

[1,k]

从

k

到

1

递减，当递减到

1

时重复。

显而易见这样构造可以使得拿到物品数最小。

设这个最小值为

s

。

s \le m

且

s

在所有满足

s \le m

中的

s

最大时，

x

也达到合法最大。

然后就可以这样二分了。

时间复杂度

O(\log m)

。

代码

CPP

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,k;
ll l,r;
bool check(ll x) {
	ll b,c;
	if(x-(n-k)<=0) b=x*(x-1)/2+1-(x-(n-k));
	else b=(x-1+x-(n-k))*(n-k)/2;
	if(x-(k-1)<=0) c=x*(x-1)/2+1-(x-(k-1));
	else c=(x-1+x-(k-1))*(k-1)/2;
  //等差数列求和公式来求[1,k-1]和[k+1,n]贡献
	return b+c+x<=m;
}
int main() {
	scanf("%lld%lld%lld",&n,&m,&k);
	l=1,r=m;
	while(l<r) {
		int mid=(l+r+1)/2;
		if(check(mid)) l=mid;
		else r=mid-1;
	}
	printf("%lld",l);
	return 0;
}

文章操作

题面

题解

代码

相关推荐

评论

CF760B