为什么TLE
  • 板块P1528 切蛋糕
  • 楼主KAWorld
  • 当前回复1
  • 已保存回复1
  • 发布时间2021/10/27 20:43
  • 上次更新2023/11/4 02:07:17
查看原帖
为什么TLE
476574
KAWorld楼主2021/10/27 20:43
#include<bits/stdc++.h>
using namespace std;
int n,m,cake[55],mouth[1030],front[1030],sum,need,waste;
inline int read()
{
	int s=0,t=1;
	char c=getchar();
	while (c<'0'||c>'9')
	{
		if (c=='-') t=-1;
		c=getchar();
	}
	while (c>='0'&&c<='9')
	{
		s=s*10+c-48;c=getchar();
	}
	return s*t;
}
inline void write(int x)
{
	if (x<0)
	{
		putchar('-');x=-x;
	}
	if (x>9) write(x/10);
	putchar(x%10+'0');
}
bool dfs(int mouths,int start)
{
	if (mouths<1) return true;
	if (sum-waste<need) return false;
	bool f=false;
	for (register int i=start;i<=n;++i)
		if (cake[i]>=mouth[mouths])
		{
			bool waste_true_or_not=false;
			cake[i]-=mouth[mouths];sum-=mouth[mouths];need-=mouth[mouths];
			if (cake[i]<mouth[1])
			{
				waste+=cake[i];waste_true_or_not=true;
			}
			if (mouth[mouths]==mouth[mouths-1]) f=dfs(mouths-1,i);
			else f=dfs(mouths-1,1);
			if (waste_true_or_not) waste-=cake[i];
			cake[i]+=mouth[mouths];sum+=mouth[mouths];need+=mouth[mouths];
			if (f) return f;
		}
	return false;
}
int main()
{
	int left,right,maxcake=-1;
	n=read();
	for (register int i=1;i<=n;++i)
	{
		cake[i]=read();maxcake=max(maxcake,cake[i]);
	}
	m=read();
	for (register int i=1;i<=m;++i) mouth[i]=read();
	sort(mouth+1,mouth+m+1);
	for (register int i=1;i<=m;++i) front[i]=front[i-1]+mouth[i];
	while (mouth[m]>maxcake) --m;
	left=1;right=m;
	while (left<=right)
	{
		int mid=(left+right)>>1;
		sum=front[m];need=front[mid];waste=0;
		if (dfs(mid,1)) left=mid+1;
		else right=mid-1;
	}
	write(right);
	return 0;
}


求大佬们帮帮蒟蒻

2021/10/27 20:43
加载中...