题解：P13212 [GCJ 2015 Qualification] Infinite House of Pancakes / [SNOW] - 75

· · 题解

写于省选 Day 1 晚。

28 + 15 + 12 = 55pts，我该在哪里停留？我问我自己。

Day 2 至少让我切一题吧。

首先分菜的收益是多一张嘴可以吃的更快，因此一定会放到空盘子里。

一个显然的观察是先把菜分好肯定是不劣的，因为输出更强的时候再集火一定不会比打一半再加杆枪来的优。

另外的每个人的输出功率相同，因此答案只与煎饼最多的人有关。

于是你分煎饼肯定要均分以最小化最大值。

那么对于指定的残留数量，我们可以得到每一堆需要分裂成的堆数，显然分裂后的堆数减一就是分裂操作的需要个数。

数据范围不大考虑直接上大力做法，直接枚举分裂后的每一堆的大小，然后计算分裂操作的次数，对每一种答案取最小值即可。

时间复杂度 O(n^2)。

#include<bits/stdc++.h>
using namespace std;
int a[1005];
void solve(int op){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    cin>>a[i];
    int ans=1000;
    for(int i=1;i<=1000;i++){
        int sum=i;
        for(int j=1;j<=n;j++)
        sum+=a[j]/i+(a[j]%i!=0)-1;
        ans=min(ans,sum);
    }
    printf("Case #%d: %d\n",op,ans);
}
int main(){
    int t;
    cin>>t;
    for(int i=1;i<=t;i++)solve(i);
    return 0;
}
// 就是因为这样，我才为了你接受委托的。
// #75

Day 2 RP++！