题解 CF1011B Planning The Expedition

Solution

考虑二分。

首先要确定二分的对象，显然二分天数较为简单。

每次找到的 \(mid\) 需要判断是否能让整队人吃饱，那就调用一个 check() 。

对于 check() ，求出每包食物可供的人数，相加后与 \(n\) 相比较。

具体操作见下。

Code

#include<iostream>

using namespace std;

#define ll long long

#define max(x,y) x>y?x:y

ll n,m,l=1,r,a[1005],q[100005],d,o,mid,b;

inline bool check(int x)

{

	ll t=0;

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

		t+=q[i]/x;

	return t>=n;

}

int main()

{

	ios::sync_with_stdio(false);

	cin>>n>>m;

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

		cin>>a[i],++q[a[i]],d=max(d,a[i]),b=max(b,q[a[i]]);

	r=b;

	while(l<=r)

	{

		mid=(l+r)/2;

		if(check(mid))

			l=mid+1,o=mid;

		else r=mid-1;

	}

	cout<<o<<"\n";

	return 0;

}

巴特西

题解 CF1011B Planning The Expedition

Solution

Code

最新文章

热门文章