Problem B. Infinite House of Pancakes
Problem's Link: https://code.google.com/codejam/contest/6224486/dashboard#s=p1
Mean:
有无限多个盘子，其中有n个盘子里面放有饼，每分钟你可以选择两种操作中的一种：
1.n个盘子里面的饼同时减少1；
2.选择一个盘子里面的饼，分到其他盘子里面去；
目标是让盘子里的饼在最少的分钟数内吃完，问最少的分钟数。
analyse:
可以分析出，先分再吃不会比先吃再分差，所以我们选择先分再吃。
首先用dp预处理，dp[i][j]表示：初始时为i个饼的盘子经过分以后最大值为j需要多少步。
然后我们就可以暴力+贪心了，枚举吃的次数(1~MAX)，对于每一个吃的次数，我们需要把每个饼都分到小于或等于这个次数。详见代码。
Time complexity: 小于 O(n^3)
Source code:
#include<iostream> #include<cstdio> #include<cmath> #include<climits> using namespace std; const int MAXN=1002; int dp[MAXN][MAXN],a[MAXN]; void pre() { for(int i=0;i<=MAXN;++i) { for(int j=1;j<i;++j) { dp[i][j]=MAXN; for(int k=1;k<i;++k) { dp[i][j]=min(dp[i][j],dp[i-k][j]+dp[k][j]+1); } } } } int main() { pre(); int t; scanf("%d",&t); for(int Cas=1;Cas<=t;++Cas) { int n; scanf("%d",&n); int maxx=INT_MIN; for(int i=1;i<=n;++i) { scanf("%d",&a[i]); maxx=max(maxx,a[i]); } int ans=INT_MAX; for(int eat=1;eat<=maxx;++eat) { int tmp=0; for(int i=1;i<=n;++i) { tmp+=dp[a[i]][eat]; } tmp+=eat; ans=min(ans,tmp); } printf("Case #%d: %d\n",Cas,ans); } return 0; }
