[CSP-S模拟测试]:Dinner（二分）

题目描述

清儿今天请好朋友们吃饭，一共$N$个人坐在坐在圆桌旁。
吃饭的第一步当然是点餐了。服务员拿来了$M$份菜单。第$i$个人阅读菜单并点出自己喜欢的菜需要花费时间$T_i$。
当一个人点完菜之后，就会把菜单传到他右手边的第一个人。
$M$份菜单是同时发出的，每个菜单只能同时被一个人阅读。
清儿希望知道如何分发菜单，才能让点餐的总时间花费最少呢？

输入格式

输入第一行是$N$和$M$，表示人数和菜单数。
输入第二行，$N$个数，表示每个人点餐所需要的时间。

输出格式

输出一个整数表示点餐花费的最小时间。

样例

样例输入1：

3 2
1 5 10

样例输出1：

样例输入2：

4 2
1 2 3 4

样例输出2：

数据范围与提示

对于$20\%$的数据，$n\leqslant 100$。
对于$60\%$的数据，$n\leqslant 10,000$。
对于$100\%$的数据，$n\leqslant 50,000,T_i\leqslant 600$。

题解

刚看到提有些麻木，显然枚举从那个点开始传菜单会$T$到飞起，那么我们就想怎么改变方式。

发现我们可以二分答案，也就是时间，然后在$judge$的时候枚举起点，挨个看，直到时间超出我们现在所二分的时间就在那个点下发下一个菜单，下发一圈之后，需要下发的菜单跟有的菜单做比较即可。

这时候我们的时间复杂度是$\Theta(\log (n\times T)\times n\times m)$，显然还是会超时（虽说数据没有说$m$有多大，但是好象是$2333$）。

那么我们接着考虑优化，显然只能在$judge$函数中进行优化，在下发菜单的时候我们没有必要一个一个的找，可以利用二分，至于如何利用呢？

我们可以考虑，先预处理出来$T_i$的前缀和，注意它是一个环，对于环的题最常用的做法就是将其复制一倍，我们直接让前缀和做差即可完成二分查找。

时间复杂度：$\Theta(\log (n\times T)\times n\times \log m)$。

期望得分：$100$分。

实际得分：$100$分。

代码时刻

#include<bits/stdc++.h>

using namespace std;

int n,m;

int a[200000];

int maxn;

int ans;

int jump(register int lft,register int rht,register int x)

{

	int flag=lft-1,res=flag;

	while(lft<=rht)

	{

		int mid=(lft+rht)>>1;

		if(a[mid]-a[flag]<=x){res=mid;lft=mid+1;}

		else rht=mid-1;

	}

	return res;

}

bool judge(register int x)

{

	register int res;

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

	{

		res=1;

		if(a[i]>x)break;

		for(register int j=i;j<=i+n-i;j++)

		{

			j=jump(j,i+n-1,x);

			if(j<i+n-1)res++;

			if(res>m)goto nxt;

		}

		return 1;

		nxt:;

	}

	return 0;

}

int main()

{

	scanf("%d%d",&n,&m);

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

	{

		scanf("%d",&a[i]);

		maxn=max(maxn,a[i]);

		a[n+i]=a[i];

	}

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

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

	register int lft=maxn,rht=a[n];

	while(lft<=rht)

	{

		register int mid=(lft+rht)>>1;

		if(judge(mid))

		{

			rht=mid-1;

			ans=mid;

		}

		else lft=mid+1;

	}

	cout<<ans<<endl;

	return 0;

}

rp++

巴特西