求助求助求助
  • 板块P1528 切蛋糕
  • 楼主KAWorld
  • 当前回复1
  • 已保存回复1
  • 发布时间2021/10/28 20:42
  • 上次更新2023/11/4 02:02:58
查看原帖
求助求助求助
476574
KAWorld楼主2021/10/28 20:42
#include<bits/stdc++.h>
using namespace std;
int n,m,cake[55],mouth[1030],temp[1030],front[1030],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');
}
inline bool dfs(int mouths,int start)
{
	if (mouths<1) return true;
	if (front[m]-waste<need) return false;
	for (register int i=start;i<=n;++i)
		if (temp[i]>=mouth[mouths])
		{
			temp[i]-=mouth[mouths];
			if (temp[i]<mouth[1]) waste+=temp[i];
			if (mouth[mouths]==mouth[mouths-1])
			{
				if (dfs(mouths-1,i)) return true;
			}
			else if (dfs(mouths-1,1)) return true;
			if (temp[i]<mouth[1]) waste-=temp[i];
			temp[i]+=mouth[mouths];
		}
	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();
	while (mouth[m]>maxcake) --m;
	sort(mouth+1,mouth+m+1);
	left=0;right=m;
	for (register int i=1;i<=m;++i) front[i]=front[i-1]+mouth[i];
	while (left<=right)
	{
		int mid=(left+right)>>1;
		need=front[mid];waste=0;
		for (register int i=1;i<=n;++i) temp[i]=cake[i];
		if (dfs(mid,1)) left=mid+1;
		else right=mid-1;
	}
	write(right);
	return 0;
}

TLE 3个点 74分,真的不会在优化了,求大佬救赎一下蒟蒻

2021/10/28 20:42
加载中...